问题

翻转一棵二叉树

示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1

思路

可以发现想要翻转它，其实就把每一个节点的左右孩子交换一下（注意孩子下面的节点是一起交换的）就可以了


关键在于遍历顺序，前中后序应该选哪一种遍历顺序？
遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果 ，注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果
这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不行，因为中序遍历会把某些节点的左右孩子翻转了两次！建议拿纸画一画，就理解了
那么层序遍历可以不可以呢？依然可以的！只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的！

解法一：递归

自上而下翻转

  1. class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         //递归函数的终止条件，节点为空时返回
  4.         if(root == null) {
  5.             return null;
  6.         }
  7.         //下面三句是将当前节点的左右子树交换
  8.         TreeNode tmp = root.right;
  9.         root.right = root.left;
  10.         root.left = tmp;
  11.         //递归交换当前节点的 左子树
  12.         invertTree(root.left);
  13.         //递归交换当前节点的 右子树
  14.         invertTree(root.right);
  15.         //函数返回时就表示当前这个节点，以及它的左右子树
  16.         //都已经交换完了
  17.         return root;
  18.     }
  19. }

自下而上翻转

  1. class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         if (root == null) {
  4.             return null;
  5.         }
  6.         TreeNode left = invertTree(root.left);
  7.         TreeNode right = invertTree(root.right);
  8.         root.left = right;
  9.         root.right = left;
  10.         return root;
  11.     }
  12. }

解法二：广度优先遍历

  1. class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         if(root == null) {
  4.             return null;
  5.         }
  6.         //将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
  7.         LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
  8.         queue.offer(root);
  9.         while(!queue.isEmpty()) {
  10.             //每次都从队列中拿一个节点，并交换这个节点的左右子树
  11.             TreeNode tmp = queue.poll();
  12.             TreeNode left = tmp.left;
  13.             tmp.left = tmp.right;
  14.             tmp.right = left;
  15.             //如果当前节点的左子树不为空，则放入队列等待后续处理
  16.             if(tmp.left!=null) {
  17.                 queue.add(tmp.left);
  18.             }
  19.             //如果当前节点的右子树不为空，则放入队列等待后续处理
  20.             if(tmp.right!=null) {
  21.                 queue.add(tmp.right);
  22.             }
  24.         }
  25.         //返回处理完的根节点
  26.         return root;
  27.     }
  28. }

解法三：深度优先遍历

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            int size = stack.size();

            for (int i = 0; i < size; i++) {
                TreeNode cur = stack.pop();
                TreeNode temp = cur.left;
                cur.left = cur.right;
                cur.right = temp;
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
        }
        return root;
    }