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
Solution 1: like linked list reverse.
public class Solution {
public TreeNode upsideDownBinaryTree(TreeNode root) {
TreeNode left=null, p=null, x=root;
while (x!=null) {
TreeNode nextX=x.left;
TreeNode nextL=x.right;
x.right=p;
x.left=left;
p=x;
x=nextX;
left=nextL;
}
return p;
}
}
没有评论:
发表评论