Invert a binary tree.

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

to

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

####Recursive solution

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null){return null;}

TreeNode left = root.left;
TreeNode right = root.right;
root.left = invertTree(right);
root.right = invertTree(left);
return root;
}
}

####Iterative Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null){return null;}

// BFS/level order traversal if using a queue, DFS if using a stack
Queue<TreeNode> queue = new LinkedList<TreeNode>();

queue.add(root);

while(queue.peek() != null){
TreeNode cur = queue.poll();
TreeNode temp = cur.left;
cur.left = cur.right;
cur.right = temp;
if (cur.left != null){
queue.add(cur.left);
}
if (cur.right != null){
queue.add(cur.right);
}
}

return root;
}
}