9/29 (금) 순회 결과로부터 역으로 트리 구하기 TIL

공부한 것

• LeetCode #105. Construct Binary Tree from Preorder and Inorder Traversal

  LeetCode - The World's Leading Online Programming Learning Platform

  Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

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

  

  이진 트리의 전위와 중위 순회 결과 배열을 가지고 역으로 원본 트리를 유추하는 문제다.

  진행중이고, 다음과 같이 생각해봤는데 이 쪽으로는 가망이 없는 것 같긴 하다:

  일단 같은 자리에 Pre[3,9], In[9,3]이렇게 순서만 바뀐 노드가 오는 때는 반드시 [3,9,null]의 부모-왼자식 관계가 확정된다.
  노드를 2개씩 짝지어 서브 트리를 그려 가능한 경우의 수를 짝지어 전체 트리를 그려봤지만 일관되게 설명하기엔 복잡하다.
  일단 preorder 배열의 연이은 두 값이 만들 수 있는 관계는 뒤의 값을 기준으로:
  1. 왼쪽 자식이 된다
  2. 외동 오른 자식이 된다
  3. 왼 형제가 있는 오른 형제가 된다
  의 세 가지가 가능하고, 
  inorder 배열의 연이은 두 값은 역시나 뒤의 값을 기준으로 앞의 값과의 관계가: 
  1. 오른 자식이 된다
  2. 왼 자식의 부모가 된다
  3. 오른 자식의 n대 왼 자손이 된다
  이렇게 세 가지가 가능하다.

---

서울 할머니 댁을 다녀와서 저녁 늦게 시작하여 푸는 시간이 부족했다. 그럼에도 불구하고 한 시간 가까이 생각했는데 이렇게 헤매고 있다니… 이 정도 문제는 40분, 20분 안에도 풀어야 한다고 알고리즘 풀이 책에서는 그러던데 알고리즘 문제를 푼 날 수가 꽤 됨에도 아직 이러고 있으니 조금 우울하다.

Uploaded by N2T