[leetcode 105] Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

preorder와 inorder 배열보고 본래 이진 트리 구현하기

 

Note:
You may assume that duplicates do not exist in the tree.

For example, given

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

Return the following binary tree:

 

 

 

 

 

 

 

 

풀이:

- 난이도는 medium이었지만 몹시 어려웠다. 

- dfs와 inorder preorder의 개념이 혼합된 문제

- 핵심 개념: 

inorder는 왼쪽 서브트리 -> 루트 -> 오른쪽 서브 트리

preorder는 루트 -> 왼쪽 서브트리 -> 오른쪽 서브 트리

 

1. preorder의 0번째 인덱스는 항상 트리의 루트이다. preorder의 인덱스를 preIdx라 설정

2. inorder에서 루트 노드에 해당하는 값을 찾는다. 루트노드를 중심으로 루트노드 왼쪽에 위치한 인덱스들은 왼쪽 서브트리를, 오른쪽에 위치한 인덱스들은 오른쪽 서브트리를 구성한다.

=> 알고리즘

1. preIdx = 0; root = preorder[preIdx]

2. preorder[preIdx]로 새로운 루트 노드를 만든다. => new root

2. find root in inorder. inIdx는 루트노드의 인덱스

3. new root의 왼쪽 서브트리는 시작점부터 inIdx-1까지를 이용해서 제작

오른쪽 서브트리는 inIdx +1 부터 끝지점까지 이용해서 제작

4. 다음 루트 노드의 인덱스는 왼쪽 서브트리의 경우 preIdx+1

오른쪽 서브 트리의 경우 루트노드 인덱스는 preIdx + 서브트리 길이 +1

 

 

 

 

 

 

 

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* DFS(int preIdx, int start, int end, vector<int>& preorder,vector<int>& inorder){
        int n= preorder.size();
        if(start>end || preIdx > n -1){
            return nullptr;
        }
        
        TreeNode* cur = new TreeNode(preorder[preIdx]);
        
        int inIdx = 0;
        for(int i=0; i<n; i++){
            if(inorder[i]==preorder[preIdx]){
                inIdx = i;
            }
        }
        
        cur -> left = DFS(preIdx+1, start, inIdx-1, preorder, inorder);
        cur -> right = DFS(preIdx + inIdx-start+1, inIdx+1, end, preorder, inorder);
        
        return cur;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        return DFS(0,0,n-1,preorder, inorder);
    }
};

 

 

 

참고: www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/

Construct Tree from given Inorder and Preorder traversals - GeeksforGeeks