Leetcode: Flatten Binary Tree to Linked List
Given a binary tree, perform pre-order traversal and flatten it to a linked list such that right for each node is the next node.
In the naive solution O(n) space complexity, we just perform a pre-order traversal (current node, left, right) through the tree and add every node as we visit them. Then in a final pass, set the left to None for each node and right to the next node in the list - except for the last node where right stays None.
# 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
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if root is None:
return
visited = []
self.inner(root, visited)
for idx in range(len(visited)):
visited[idx].left = None
if idx < len(visited) - 1:
visited[idx].right = visited[idx + 1]
def inner(self, root: Optional[TreeNode], visited: List[TreeNode]) -> None:
if root is None:
return
visited.append(root)
self.inner(root.left, visited)
self.inner(root.right, visited)# 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
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
self.inner(root)
def inner(self, root: Optional[TreeNode]) -> None:
curr = root
while curr is not None:
if curr.left is not None:
prev = curr.left
while prev.right is not None:
prev = prev.right
prev.right = curr.right
curr.right = curr.left
curr.left = None
curr = curr.right