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
一刷
題解：
方法1: recursive
recursive
newRoot存在的意義是keep住最left的leaf
public TreeNode upsideDownBinaryTree(TreeNode root) {
if(root == null || root.left == null) {
return root;
}
TreeNode newRoot = upsideDownBinaryTree(root.left);
root.left.left = root.right; // node 2 left children
root.left.right = root; // node 2 right children
root.left = null;
root.right = null;
return newRoot;
}
方法2： iterative
注意日戈，temp在上一輪中就要保存好，避免被overwritten.
iterative
public TreeNode upsideDownBinaryTree(TreeNode root) {
TreeNode curr = root;
TreeNode next = null;
TreeNode temp = null;
TreeNode prev = null;
while(curr != null) {
next = curr.left;
// swapping nodes now, need temp to keep the previous right child
curr.left = temp;
temp = curr.right;
curr.right = prev;
prev = curr;
curr = next;
}
return prev;
}
二刷
遍歷順序?yàn)椋簂eft-root
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
if(root == null || root.left == null) return root;
TreeNode newRoot = upsideDownBinaryTree(root.left);
root.left.left = root.right;
root.left.right = root;
root.left = null;
root.right = null;
return newRoot;
}
}
