114. Flatten Binary Tree to Linked List

LeetCode Link (opens in a new tab)

Tree Recursion

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 cases

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

Approach

주어진 이진트리를 pre-order 탐색의 순서로 연결리스트 처럼 만드는 문제이다. pre-order traversal은 노드-왼쪽 서브트리-오른쪽 서브트리 순으로 방문하는 트리 탐색 방법이다.
연결리스트처럼 트리를 만드는 방법은 모든 노드를 루트 노드를 시작으로 right 포인터만으로 일렬로 이어지도록 만들면 된다.
접근 방법은 pre-order 순서기 때문에 left 포인터가 있는 경우 left 서브트리를 현재 노드의 right 포인터로 만들고 left를 null로 만든다. 그럼 원래 right에 있던 서브트리는 잠시 임시 변수에 저장해 두었다가 right에 붙인 서브트리의 가장 오른쪽 끝에 붙인다.
그 다음 재귀적으로 위 과정을 반복하면 된다. right 서브트리를 오른쪽 끝에 붙이는 이유는 pre-order 탐색 순서를 보장하기 위해서이다. 재귀적으로 탐색했을 때, 결과적으로 왼쪽 서브트리를 모두 탐색한 다음 오른쪽 서브트리를 탐색하게 된다.

Solution Code

var flatten = function(root) {
  const preorder = (node) => {
    if (!node) {
      return
    }
 
    if (node.left) {
      const tmp = node.right
      node.right = node.left
      node.left = null
      let cur = node.right
      while (cur.right) {
        cur = cur.right
      }
      cur.right = tmp
    }
    preorder(node.right)
  }
 
  preorder(root)
};

Complexity

• time complexity : $O(n)$
• space complexity : $O(1)$