226. Invert Binary Tree

Invert a binary tree.

Example:

Input:

     4
   /   
  2     7
 /    / 
1   3 6   9

Output:

     4
   /   
  7     2
 /    / 
9   6 3   1

 1 //Time: O(n), Space: O(h)/O(logn) 
 2 //Approach 1: DFS Top down recursive
 3    public TreeNode invertTree(TreeNode root) {
 4         if (root == null) {
 5             return null;
 6         }
 7         
 8         TreeNode temp = root.left;
 9         root.left = invertTree(root.right);
10         root.right = invertTree(temp);
11         return root;
12     }
13 
14 //Approach 2: DFS Bottom up recursive(Divide and Concur)
15     public TreeNode invertTree(TreeNode root) {
16         if (root == null) {
17             return null;
18         }
19         
20         TreeNode left = invertTree(root.left);
21         TreeNode right = invertTree(root.right);
22         root.left = right;
23         root.right = left;
24         return root;
25     }
26 //Approach3: BFS Queue, 省略