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
思路：先找到新二叉树的根节点，上层的父节点通过栈来记录，找到新的根节点以后，不断弹出栈顶，来构造新的二叉树。
public TreeNode upsideDownBinaryTree(TreeNode root) {
if (root == null) {
return root;
}
Stack<TreeNode> parents = new Stack<>();
//find new root
TreeNode dummy = root;
while (dummy.left != null) {
parents.push(dummy);
dummy = dummy.left;
}
TreeNode newRoot = dummy;
//构造新树
TreeNode newDummy = newRoot;
while (!parents.empty()) {
TreeNode cur = parents.pop();
newDummy.right = cur;
newDummy.left = cur.right;
cur.right = null;
cur.left = null;
newDummy = newDummy.right;
}
return newRoot;
}