Flatten Binary Tree to Linked List
114. Flatten Binary Tree to Linked List
Difficulty: Medium
Related Topics: Linked List, Stack, DFS, Tree, Binary Tree
Given the root of a binary tree, flatten the tree into a “linked list”:
The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The “linked list” should be in the same order as a pre-order traversal of the binary tree.
Example 1:
Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [0] Output: [0]
Code:
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
temp = []
def dfs(root):
stack = []
stack.append(root)
while stack:
curr = stack.pop()
if curr:
temp.append(curr.val)
if curr.right:
stack.append(curr.right)
if curr.left:
stack.append(curr.left)
dfs(root)
def replace(root, temp):
stk = []
stk.append(root)
i=1
while stk and i < len(temp):
curr = stk.pop()
if curr:
if curr.right:
curr.right.val = temp[i]
stk.append(curr.right)
i+=1
elif curr.right == None:
curr.right = TreeNode(temp[i])
stk.append(curr.right)
i+=1
if curr.left:
curr.left = None
replace(root, temp)
Feedbacks:
I first traversed a tree as a pre-order traverse and saved the values to the list. At second loop through the tree, if I encounter left node, I delete, or if I encounter right node, I replace its value by corresponding value which is stored in the list in order.