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:
Related Problems
Given the head of a linked list, remove the nth node from the end of the list and return its head.
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.