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
/ \
2 3
/ \
4 5
return the root of the binary tree [4,5,2,#,#,3,1].
4
/ \
5 2
/ \
3 1
思路：
屏幕快照 2017-09-06 下午9.28.14.png
Solution1：递归实现
Time Complexity: O(N) Space Complexity: O(N) 递归缓存
Solution2：Iterative实现
Time Complexity: O(N) Space Complexity: O(1)
Solution1 Code：
class Solution1 {
public TreeNode upsideDownBinaryTree(TreeNode root) {
if(root == null || root.left == null) {
return root;
}
TreeNode newRoot = upsideDownBinaryTree(root.left);
root.left.left = root.right; // 1st change
root.left.right = root; // 2nd change
root.left = null;
root.right = null;
return newRoot;
}
}
Solution2 Code：
class Solution2 {
public TreeNode upsideDownBinaryTree(TreeNode root) {
if(root == null) return null;
TreeNode cur = root;
TreeNode prev = null;
TreeNode save_prev_right = null;
while(cur != null) {
TreeNode next = cur.left;
cur.left = save_prev_right;
save_prev_right = cur.right;
cur.right = prev;
prev = cur;
cur = next;
}
return prev;
}
}
