226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

思路

想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。

关键在于遍历顺序，前中后序、层序应该选哪一种遍历顺序？

注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果

这道题目使用前序遍历、后序遍历和层序遍历都可以，唯独递归中序遍历不行，因为中序遍历会把某些节点的左右孩子翻转了两次！

不过中序遍历翻转两次也是可以的。

解法

1. 递归

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return root;
    }
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
}

2. 迭代

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode node = root;
        deque.offer(node);
        TreeNode tmpNode = null;
        while (!deque.isEmpty()) {
            node = deque.poll();
            tmpNode = node.left;
            node.left = node.right;
            node.right = tmpNode;
            if (node.left != null) {
                deque.offer(node.left);
            }
            if (node.right != null) {
                deque.offer(node.right);
            }
        }
        return root;
    }
}