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

Identifying the Problem

이진트리의 preorder 순회 결과와 inorder 순회 결과를 가지고 원래 트리를 만든다.

 

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 

Output: [3,9,20,null,null,15,7]

Organizing thoughts

탐색

preorder[0]은 트리의 root부분이다.

나머지 부분은 root의 자식 node이다.

임의로 inorder의 요소를 pivot으로 지정했을 때

inorder[0] ~ inorder[pivot-1]의 값들은 pivot의 왼쪽에 위치하고,

inorder[pivot+1] ~ inorder[size-1]의 값들은 pivot의 오른족에 위치한다.

inorder[pivot] 왼쪽에 아무것도 없다면, 왼쪽 자식 노드는 null이고,

inorder[pivot] 오른쪽에 아무것도 없다면, 오른쪽 자식 노드는 null이다.

 

흐름

preorder = [3,9,20,5,7] , inorder = [9,3,5,20,7] 이라면,

pre를 level 별로 놓는다.

 

level	val	val
0	3
1	9	20
2	5	7

그 후에, inorder의 정보로, 자식노드를 결정한다.

순서는 preorder의 순서대로 진행한다.

 

처음 3은 inorder[1]에 위치하고,

inorder[1] 이전은 모두 3 left에 위치, 이후는 모두 right에 위치함을 알 수 있다.

 

다음 9는 inorder[0]에 위치하고,

inorder[0] 왼쪽에 아무것도 없으므로, 왼쪽 노드는 null,

오른쪽에는 3이 있지만, 이미 부모 노드인 것을 확인했으므로 오른쪽 노드도 null이다.

 

다음 20은 inorder[3]에 위치하고,

inorder[3] 이전은 모두 20 left에 위치, 이후는 모두 right에 위치함을 알 수 있다.

왼쪽에 9,3,15가 있지만, 이 중 9,3은 이전에 파악했으므로 왼쪽에 5만 있다고 생각한다.

 

다음 5는 inorder[2]에 위치하고,

왼쪽에 9,3이 있지만, 모두 이전에 파악했으므로, 왼쪽 노드는 null이다.

오른쪽에 20,7이 있지만, 20은 5의 부모노드인 것을 확인했으므로 오른쪽에도 아무것도 없다.

따라서 오른쪽 노드도 null이다.

 

마지막 7은 inorder[4]에 위치하고,

왼쪽은 이미 다 파악했고, 오른쪽은 아무것도 없어 둘다 null이 된다.

Sourcecode

## 정답 코드 및 출처

C++ simple recursive (+ detail explanation) - LeetCode Discuss

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int index = 0; //preorder의 요소를 level 순으로 탐색
        return build(preorder, inorder, index, 0 , inorder.size() - 1);
    }
    TreeNode* build(vector<int>& preorder, vector<int>& inorder,int &index, int left, int right)
    {
        if(left > right) return NULL; //왼쪽 혹은 오른쪽에 아무것도 없다면, null 리턴
        
        int pivot = left; // pivot 초기화
        
        while(inorder[pivot] != preorder[index]) pivot++;
        //preorder[index] 값과 inorder의 같은 부분을 탐색
        
        index++;
        
        TreeNode* node = new TreeNode(inorder[pivot]);
        node->left = build(preorder, inorder, index, left , pivot-1);
        node->right = build(preorder, inorder, index, pivot+1 , right);
        //중위순회로 tree생성
        return node;
    }
};