114 Flatten Binary Tree to Linked List – Medium
Problem:
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
Thoughts:
Idea is to use a modified preorder walk of the tree. Root, left, right.
Have a global pointer that keeps the node that needs a new right child to insert.
Solutions:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
TreeNode pointer = new TreeNode(-1);
public void flatten(TreeNode root) {
flattenTree(root);
}
private void flattenTree(TreeNode node){
if (node != null){
TreeNode left = node.left;
TreeNode right = node.right;
node.left = null;
node.right = null;
pointer.right = node;
pointer = node;
flattenTree(left);
flattenTree(right);
}
}
}
Non-Recursion version:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public void flatten(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = new TreeNode(-1);
TreeNode node = root;
while (true) {
if (node == null) {
if (stack.size() == 0) {
break;
}
node = stack.pop();
}
p.right = node;
p = node;
if (node.right != null) {
stack.push(node.right);
}
node = node.left;
p.left = null;
}
}
}