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
    
      q = new LinkedList
     
      ();        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;    }}