翻转二叉树

2015年，Homebrew 的作者 Max Howell 在 Twitter 上发布了一条消息：

brew作者在Google挂了，还发twitter说，Google面试官说：对不起，虽然我们全公司的人都在用你的brew但是你竟然不能写出反转二叉树的代码，所以，滚吧。

你可以在leetcode上做这道题，有一种答案只需要8行代码。这个题目的难度属于Easy，根据leetcode的定义，如果Easy难度的题目无法在面试中答出来，确实是拿不到Offer的。

https://leetcode-cn.com/problems/invert-binary-tree/

从这道题我们可以看到，图中的左右子树进行了互换，而且是最大的树之内的任何一个子树而言，它的左右子树也都进行了反转。

一、递归

步骤如下：

• 翻转根节点的左子树（递归调用当前函数）
• 翻转根节点的右子树（递归调用当前函数）
• 交换根节点的左子节点与右子节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree (TreeNode root) {

      if (root == null)
         return null;

      invertTree(root.left);//翻转根结点的左子树
      invertTree(root.right);//翻转根结点的右子树

      TreeNode tmp = root.left; //交换左子节点和右子节点
      root.left = root.right;
      root.right = tmp;

      return root;
   }
}

时间复杂度，由于二叉树的每一个节点都会遍历到，所以是O(n)，n为二叉树的节点个数。
空间复杂度，由于只新开了一个变量tmp，所以空间复杂度为O(n)。

二、迭代法-队列

迭代法的思路是BFS或者DFS，实际上也是二叉树的遍历。BFS用Queue实现，DFS的话将代码中的Queue换成Stack。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
     	//LinkedList实现了集合框架的Queue接口
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        if(root!=null) q.offer(root);//加入元素
        while(!q.isEmpty()){
            TreeNode curr = q.poll();//获取并移出元素
            TreeNode tmp = curr.right;
            curr.right = curr.left;
            curr.left = tmp;
            if(curr.left!=null) q.offer(curr.left);
            if(curr.right!=null) q.offer(curr.right);
        }
        return root;
    }
}

这是一种非递归层次遍历，借助于队列，元素先进先出。时间复杂度 O(N) 空间复杂度 O(1)。

三、迭代法-栈

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

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

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);//先将根节点压入堆栈
        while (stack.size() > 0) {
     		//根据栈的先进后出操作，获取栈中最后一个元素，即最先入栈的元素
            TreeNode temp = stack.lastElement();
            stack.pop();//弹出栈顶元素

            //交换左右子树
            TreeNode tempLeft = temp.left;
            temp.left = temp.right;
            temp.right = tempLeft;

            //左子树不为空，将左子树入栈
            if (temp.left != null) {
                stack.push(temp.left);
            }
            //右子树不为空，将右子树入栈
            if (temp.right != null) {
                stack.push(temp.right);
            }
        }
        return root;

    }
}

和队列不同，这是先进后出的方式。