Given a binary tree where all the right nodes are leaf nodes, flip it upside down and turn it into a tree with left leaf nodes.
Keep in mind: ALL RIGHT NODES IN ORIGINAL TREE ARE LEAF NODE.
Keep in mind: ALL RIGHT NODES IN ORIGINAL TREE ARE LEAF NODE.
/* for example, turn these:
*
* 1 1
* / \ / \
* 2 3 2 3
* / \
* 4 5
* / \
* 6 7
*
* into these:
*
* 1 1
* / /
* 2---3 2---3
* /
* 4---5
* /
* 6---7
*
* where 6 is the new root node for the left tree, and 2 for the right tree.
* oriented correctly:
*
* 6 2
* / \ / \
* 7 4 3 1
* / \
* 5 2
* / \
* 3 1
*/
A very beautiful Tree reverse problem from Careercup.1. Traverse down to the left bottom of the tree, make it as the new root.
2. Recursively going up and reverse the tree.
1
/ \
2 3
root .val == 1;
newRoot = 2;
root.left.left ( 1.left.left = 2.left) = root.right (3)
root.left.right (1.left.right = 2.right) = root (1);
root.left = null
root.right = null
2
/ \
3 1
Update: 2015 - 01 - 02
The left leaf node will be returned as the NEW root, thus every time we need to change the pointers of the ORIGINAL root.
Technically it's possible to have a condition like this:
2
/ \
3 1
\
4
Since the problem doesn't say a left leaf node must exist...
Anyway, let's assume if this situation happens, take the node 3 as the new root and discard the poor 4...
public class BTUpsideDown { public TreeNode upsideDown(TreeNode root) { if (root == null) return root; if (root.left == null || root.right == null) return root; //traverse down to the left leave TreeNode newRoot = upsideDown(root.left); root.left.left = root.right; root.left.right = root; //root becomes leaf root.left = null; root.right = null; //System.out.println(newRoot.val); return newRoot; } }
No comments:
Post a Comment