Invert Binary Tree

Invert a binary tree.

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

to

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

Trivia: This problem was inspired by this original tweet by Max
Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

原题链接

递归法

复杂度

时间 O(N) 空间 O(N) 递归栈空间

思路

这个难倒Max Howell大神的题也是非常经典的一道测试对二叉树遍历理解的题。递归的终止条件是当遇到空节点或叶子节点时，不再交换，直接返回该节点。对于其他的节点，我们分别交换它的左子树和右子树，然后将交换过后的左子树赋给右节点，右子树赋给左节点。代码给出的是后序遍历的自下而上的交换，先序遍历的话就是自上而下的交换。

代码

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) return root;
        TreeNode newLeft = invertTree(root.right);
        TreeNode newRight = invertTree(root.left);
        root.left = newLeft;
        root.right = newRight;
        return root;
    }
}

迭代法

复杂度

时间 O(N) 空间 O(1)

思路

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

代码

public class Solution {
    public TreeNode invertTree(TreeNode root) {
        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;
    }
}