[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal (C++)

문제 링크: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=study-plan-v2&envId=top-100-liked 

LeetCode - The World's Leading Online Programming Learning Platform

1. 주의할 점

- 재귀문으로 접근하며, return 조건을 알아야 한다

- Inorder와 Preorder의 검사 범위를 따로 둬야 한다

 

2. 구현

- Preorder의 첫번째 항은 항상 Root를 것을 이용한다

- Inorder에서 Root가 어디에 위치해 있는지 찾는다

- Root를 기준으로 왼쪽 Subtree와 오른쪽 Subtree를 각각 완성한다

- 분할 정복과 같은 방식으로 Subtree에서도 위와 같은 방법으로 진행한다. 단, Preroder와 Inorder의 검사 범위가 다르므로 서로 다른 변수를 받도록 한다(Preorder: pl~pr, Inorder: il~ir)

 

class Solution {
public:
    TreeNode* makeTree(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir){
        if(pl > pr || il > ir) return nullptr;
        //get rootIdx of inorder;
        int ridx = -1;
        for(int i=il;i<=ir;i++){
            if(inorder[i]==preorder[pl]){
                ridx = i;
                break;
            }
        }
        TreeNode* node = new TreeNode(preorder[pl]);
        int leftLen = ridx-il;
        node->left = makeTree(preorder, inorder, pl+1, pl+leftLen, il, ridx-1);
        node->right = makeTree(preorder, inorder, pl+leftLen+1, pr, ridx+1, ir);

        return node;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()) return nullptr;
        int len = preorder.size();

        return makeTree(preorder, inorder, 0, len-1, 0, len-1);
    }
};