114. Flatten Binary Tree to Linked List

Description

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

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

💡 Hint 1:
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

Submitted Code

# 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.
        """
        rights = []                         # 오른쪽 서브트리 루트 저장

        while root:
            if root.right:                  # 오른쪽 자식 있을 때
                rights.append(root.right)

            if root.left:                   # 왼쪽 자식 있을 때
                next_node = root.left
                root.right = next_node
                root.left = None
                root = next_node
            elif rights:
                root.right = rights.pop()
                root = root.right
            else:
                break

Runtime: 0 ms | Beats 100.00%
Memory: 19.60 MB | Beats 43.29%

오른쪽 서브트리 루트만 스택에 저장하고 더 이상 왼쪽 서브트리가 없을 때 꺼내서 연결하는 방법을 사용했다.

Other Solutions

1st

class Solution:
    def flatten(self, root: TreeNode) -> None:
        curr = root
        while curr:
            if curr.left:
                runner = curr.left
                while runner.right: runner = runner.right
                runner.right, curr.right, curr.left = curr.right, curr.left, None
            curr = curr.right

time complexity: 𝑂(𝑛)
space complexity: 𝑂(1)

스택이나 재귀 없이 Morris Traversal과 비슷하게 푸는 방법이다.

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

    1 (curr)                    1
   / \                         / \
  2   5     →     2      →    n   2
 / \   \         / \             / \
3   4   6       3   4           3   4 
                     \               \
                      5               5
                       \               \
                        6               6

1               1
 \               \
  2 (curr)        2
 / \       →       \
3   4               3
     \               \
      5               4
       \               \
        6               5
                         \
                          6

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

2nd

class Solution:
    def __init__(self):
        self.prev = None
        
    def flatten(self, root: Optional[TreeNode]) -> None:
        
        if not root: return 
        self.flatten(root.right)
        self.flatten(root.left)
        root.right = self.prev
        root.left = None
        self.prev = root        

time complexity: 𝑂(𝑛)
space complexity: 𝑂(ℎ)

원래 전위 순회 root -> left -> right를 뒤집어서 right -> left -> root로 돌면서 연결 리스트를 뒤에서부터 조립하는 방법이다.