Leetcode[114] Flatten Binary Tree to Linked List
08 Nov 2015###Task1 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 click to show hints.
Hints: If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.
###Python ####Iterative
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
if not root:
return
stack = []
cur = root
while len(stack) > 0 or cur:
if cur.right:
stack.append(cur.right)
if cur.left:
cur.right = cur.left
cur.left = None
elif len(stack) > 0:
cur.right = stack.pop()
cur = cur.right
####Recursive
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
self.flat(root)
def flat(self, root):
if not root:
return None
r = self.flat(root.right)
l = self.flat(root.left)
root.left = None
root.right = l
dum = root
while dum.right:
dum = dum.right
dum.right = r
return root
###Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode convert(TreeNode root) {
if (root == null) {
return null;
}
TreeNode right = convert(root.right);
root.right = convert(root.left);
root.left = null;
TreeNode tempRoot = root;
while (tempRoot.right != null) {
tempRoot = tempRoot.right;
}
tempRoot.right = right;
return root;
}
public void flatten(TreeNode root) {
convert(root);
}
}
###Points
- O(n)
- Divide and conquer
- Back up right if right exists, then move left to right if left exists; otherwise pop from stack then add to right