LC156. Binary Tree Upside Down
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
重新排列一棵二叉树，就是对于一个节点，左儿子变成其父节点，右儿子变成其左兄弟。从root开始进行这一变化。
For each node in its loop, current node’s left child should be its parent’s right child, current node’s right child should be its parent, and record the right child and itself, go to its left child do the same thing.
Loop solution:
/**
* 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) {
// for each node, its left child becomes its parent, its right child become its left brother
if(root == null || root.right == null && root.left == null) return root;
TreeNode node = root, parent = null, right = null;
while(node != null){
TreeNode left = node.left;
node.left = right;
right = node.right;
node.right = parent;
parent = node;
node = left;
} // while
return parent;
}
}
最后的根是最左边的节点，循环不断向左进行。O(n).
Recursive solution:
同样的算法，利用递归寻找新的根并返回。O(n).
/**
* 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) {
// for each node, its left child becomes its parent, its right child become its left brother
if(root == null || root.left == null && root.right == 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;
}
}