공부한 것
- LeetCode #105. Construct Binary Tree from Preorder and Inorder TraversalLeetCode - The World's Leading Online Programming Learning PlatformLevel 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