Misc

114. Flatten Binary Tree to Linked List

Medium·

Flatten binary tree to linked list

M

114Flatten Binary Tree to Linked List

4 Approaches

Sentinel + Preorder

O(n) timeO(h) aux

Recursive with Tail Return

O(n) timeO(h) aux

Iterative Stack

O(2n) timeO(h) aux

Morris-like (Space Optimized)

O(n) timeO(1) aux

FIG. FLATTEN BINARY TREE TO LINKED LIST● INTERACTIVE

visualization loads as you reach it

class Solution:

def flatten(self, root: Optional[TreeNode]) -> None:

def rec(node):

nonlocal curr

if node:

curr.right = node

curr = curr.right

left, right = curr.left, curr.right

curr.left = curr.right = None

rec(left)

rec(right)

 

sentinel = curr = TreeNode(None)

rec(root)

return sentinel.right

---