226. Invert Binary Tree

Problem:
Invert a binary tree.

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

to

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

4/24/2018 update:
If we do swap first then recuse, we need to follow the regular temp swap approach. However, if we do invert first then cache the return TreeNode, we no longer need temp.

Iterative solution:
null assign to null is allowed. but null's left or right is not allowed.

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            TreeNode temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
            if (cur.left != null) {
                queue.offer(cur.left);
            }   
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
        return root;
    }
}

Solution:

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