[LC] 105. Construct Binary Tree from Preorder and Inorder Traversal

[seungriyou]

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Approach

Idea 1

ref: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/981152/recursion-explanation-visuals-python

preorder 혹은 inorder 중 하나만으로는 unique 하게 binary tree를 결정할 수 없다. 따라서 두 가지를 모두 사용하여 tree를 결정해야 한다.

preorder와 inorder 간 관계를 살펴보기 위해, 예를 들어 확인해보자.

img src

• 우선, preorder와 inorder의 순회 순서는 다음과 같다.

  구분	순서 ([..]에 주목!)
  preorder	[root - left] - right
  inorder	[left - root] - right

• preorder의 첫 번째 원소는 root가 된다.

• preorder에서 찾은 root에 해당하는 값을 inorder에서 찾으면, 그 값을 기준으로 왼쪽은 left subtree, 오른쪽은 right subtree를 구성하게 된다. 이때, inorder에서 찾은 root의 index를 root_idx라 하자.

  inorder의 index	~ root_idx - 1	root_idx	root_idx + 1 ~
  	left subtree	root	right subtree
  	inorder[:root_idx]	inorder[root_idx]	inorder[root_idx + 1:]

• preorder에서는 root로 찾은 첫 번째 원소를 제외하고, root_idx 위치까지가 left subtree, 그 이후가 right subtree를 구성하게 된다.

  preorder의 index	0	1 ~ root_idx	root_idx + 1 ~
  	root	left subtree	right subtree
  	preorder[0]	preorder[1:root_idx + 1]	preorder[root_idx + 1:]

• 이렇게 찾은 규칙에 따라 recursive 한 로직을 작성할 수 있다.

  • base condition:

    1. preorder(혹은 inorder)가 비어있을 때: None 반환
    2. preorder의 길이가 1일 때: leaf node이므로 TreeNode(preorder[0]) 반환

  • tree 구성:

    1. preorder[0]로 root 노드 생성
    2. inorder에서 root_idx 찾기
    3. root.left, root.right 찾기

Idea 2

ref: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/2279180/python-explained

혹은, preorder에 대해서는 맨 앞의 원소만 root로 pop 하면서 사용할 수도 있다. (preorder.pop(0) or preorder 뒤집고 preorder.pop())

어차피 preorder를 사용하는 목적은 root를 찾기 위함이기 때문이다.

이렇게 작성할 때는 inorder가 비어있지 않다면 동작을 수행하는 형태로 작성한다.

[!tip] 예시를 직접 확인하면서 규칙을 찾아보자!

[!note] index를 hash table에 기록하고 pointer를 사용한다면, .index()를 사용하지 않고 O(1)에 위치를 찾음으로써 time optimize, slicing 할 필요도 없어 space optimize도 가능할 것 같다.

혹은 deque를 사용할 수도?

이건 나중에..

ref: link1 / link2

Complexity

• Time: O(n^2)? (.index() 때문에.. 잘 모르겠음 (ref))
• Space: O(n^2) (list split 시 최악의 경우)