flatten-binary-tree-to-linked-list.sh — zsh
← listnormal view →

Flatten Binary Tree to Linked List

medium
Longest Common Subsequence01 Matrix
binary-treedepth-first-searchlinked-listrecursion

Given the root of a binary tree, flatten the tree in place so it becomes a "linked list" that uses the tree's right pointers to point to the next node in preorder traversal order. After flattening, every node's left child must be null.

Return the same root, now mutated into that right-leaning chain.

Input / output

  • Input: root: TreeNode where the JSON test fixture is a LeetCode-style level-order array using null for missing children, for example [1,2,5,3,4,null,6].
  • Output: TreeNode, also serialized as a LeetCode-style level-order array using null for missing children. Since the flattened tree has only right children, the output literally looks like a chain such as [1,null,2,null,3,null,4,null,5,null,6].
  • Trailing null values are trimmed in the serialized output, so an empty tree is represented as [].

Examples

  1. root = [1,2,5,3,4,null,6] returns [1,null,2,null,3,null,4,null,5,null,6] because the preorder traversal is 1,2,3,4,5,6.
  2. root = [1,2,null,3] returns [1,null,2,null,3].
  3. root = [] returns [].

Constraints

  • 0 <= number of nodes <= 2000
  • -100 <= Node.val <= 100

Follow-up Can you do this in O(1) extra space using Morris-traversal-style threading instead of recursion or an explicit stack?

Examples
Example 1: empty tree
Input: root = []
Output: []
Example 2: single node
Input: root = [1]
Output: [1]
Example 3: classic preorder flatten
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]