114.Flatten_Binary_Tree_to_Linked_List(Medium).md

114. Flatten Binary Tree to Linked List (Medium)

Date and Time: Nov 19, 2024, 15:00 (EST)

Link: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

Question:

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.

Example 1:

Input: root = [1,2,5,3,4,null,6]

Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = []

Output: []

Example 3:

Input: root = [0]

Output: [0]

Constraints:

• The number of nodes in the tree is in the range [0, 2000].

• -100 <= Node.val <= 100

Walk-through:

Example 1:
        1
      /   \
    2       5
  /   \       \
3       4       6

1. Find curr (1)'s left-subtree's rightmost node (4), and set this right-most node.right to curr's right subtree.
        1
      /
    2 
  /   \
3       4 
          \
            5
              \
                6

2. Set curr's right to be curr's left, and set curr = curr.right.
        1
          \
            2 
          /   \
        3       4 
                  \
                    5
                      \
                        6

3. Repeat the above steps, now curr = 2. Find curr's left-subtree's right-most node and set its right to be curr.right.
        1
          \
            2 
          /
        3      
          \ 
            4 
              \
                5
                  \
                    6

4. Set curr.right = curr.left, and set curr = curr.right to continue.
        1
          \
            2
              \ 
                3
                  \       
                    4 
                      \
                        5
                          \
                            6

Python Solution:

# 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.
        """
        # pre-order traversal: root->left->right
        # repeatly set curr's left-subtree rightmost node to be curr's right-subtree
        # then set curr.right = curr.left, and update curr = curr.right

        # TC: O(n), n is total nodes, SC: O(1)
        while root:
            # Check if left-subtree exists
            if root.left:
                prev = root.left
                # Find the left subtree's right most node
                while prev.right:
                    prev = prev.right
                prev.right = root.right
                root.right = root.left
            # Update root.left and root to next node
            root.left = None
            root = root.right

Time Complexity: $O(n)$
Space Complexity: $O(1)$