Flatten a binary tree into a pre order traversal linked list
Home | Coding Interviews | Simple Data Structures | Flatten a binary tree into a pre order traversal linked list
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.
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Input: root node of binary tree
Output: convert binary tree to right-skewed linked list
"""
# record of node of previous traversal
previous_traversal = None
def helper( node):
if node:
# DFS travesal to next level
helper( node.right )
helper( node.left )
# flattern binary tree to right skewed linked list
nonlocal previous_traversal
node.right = previous_traversal
node.left = None
previous_traversal = node
# ---------------------
helper(root)The explanation video uses java but covers same technique:
Another unique approach where the recursive function returns two nodes to help connect the end of the list:
Posted by Jamie Meyer 19 days ago