156 Binary Tree Upside Down

156. Binary Tree Upside Down

1. Question

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
For example:
Given a binary tree{1,2,3,4,5},
1
1
2
/ \
3
2 3
4
/ \
5
4 5
Copied!
return the root of the binary tree[4,5,2,#,#,3,1].
1
4
2
/ \
3
5 2
4
/ \
5
3 1
Copied!

2. Implementation

(1) Recursion
1
class Solution {
2
public TreeNode upsideDownBinaryTree(TreeNode root) {
3
if (root == null || root.left == null) {
4
return root;
5
}
6
7
TreeNode newRoot = upsideDownBinaryTree(root.left);
8
root.left.left = root.right;
9
root.left.right = root;
10
root.left = null;
11
root.right = null;
12
return newRoot;
13
}
14
}
Copied!
(2) Iteration
1
class Solution {
2
public TreeNode upsideDownBinaryTree(TreeNode root) {
3
TreeNode curNode = root, preNode = null, nextNode = null, tempNode = null;
4
5
while (curNode != null) {
6
nextNode = curNode.left;
7
8
curNode.left = tempNode;
9
tempNode = curNode.right;
10
curNode.right = preNode;
11
preNode = curNode;
12
curNode = nextNode;
13
}
14
return preNode;
15
}
16
}
Copied!

3. Time & Space Complexity

Recursion: 时间复杂度O(h), 空间复杂度O(h)
Iteration: 时间复杂度O(h), 空间复杂度O(1)