Flatten Binary Tree to Linked List
franklinqin0 TreeDFSMorris
# Definition for a Binary Tree Node
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
1
2
3
4
5
2
3
4
5
# Solution
Let be the number of nodes in the tree.
Do not return anything, modify root in-place instead.
# Recursive DFS
First preorder traverse the tree and store the result in lst
. Then set every node's left
to None
and right
to the next node.
Complexity
time:
space:
def flatten(self, root: TreeNode) -> None:
lst = []
def preorder(node: TreeNode):
if not node: return
lst.append(node)
preorder(node.left)
preorder(node.right)
preorder(root)
for i in range(1, len(lst)):
lst[i-1].left = None
lst[i-1].right = lst[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# Reverse Preorder Traversal
Solve the right subtree before the left. After a subtree is flattened, the root is left appended to self.prev
.
Complexity
time:
space: (due to implicit stack space)
self.prev = None
def flatten(self, root: TreeNode) -> None:
if not root:
return None
self.flatten(root.right)
self.flatten(root.left)
# point to the prev ordered tree
root.right = self.prev
# remove the left part of current node
root.left = None
# add root to ordered tree
self.prev = root
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# Follow Up
Can you flatten the tree in-place (with extra space)?
# Morris Traversal
Since the problem asks for rewiring instead of traversing, the following algorithm is simpler than the standard Morris Traversl algorithm.
Complexity
time:
space:
def flatten(self, root: TreeNode) -> None:
# handle the null scenario
if not root:
return None
node = root
while node:
# if the node has a left child
if node.left:
# find the rightmost node of left subtree
rightmost = node.left
while rightmost.right:
rightmost = rightmost.right
# rewire the connections
rightmost.right = node.right
node.right = node.left
node.left = None
# move on to the right side of the tree
node = node.right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18