Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
Hints:If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.
public void flatten(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
TreeNode runner = root;
while(runner!=null){
if(runner.left!=null){
findRightMostChild(runner.left).right = runner.right;
runner.right = runner.left;
runner.left = null;
}
runner = runner.right;
}
}
public TreeNode findRightMostChild(TreeNode node){
while(node.right!=null){
node = node.right;
}
return node;
}
