Invert binary tree

, , , , , ,

Question

Invert a binary tree.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
input: 
     4
   /   \
  2     7
 / \   / \
1   3 6   9

output:

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

Solution

We just need to swap left and right at each time, at the end we just need return root.

Code

1
2
3
4
5
6
7
8
9
10
11
12
// time:O(n) space:O(n)
public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        // swap
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }