LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

문제

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

걸린 시간

-

풀이

C++

/**
 * 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) {}
 * };
 */
struct Order {
    vector<int> pre, in;
    Order() {}
    Order(vector<int> pre, vector<int> in) : pre(pre), in(in) {}
};
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        Order subTree(preorder, inorder);
        return makeTree(subTree);
    }
    TreeNode* makeTree(Order subTree){
        if(subTree.pre.size() == 0) return nullptr;

        int rootNode = subTree.pre.front();
        TreeNode* root = new TreeNode(rootNode);
        if(subTree.pre.size() == 1) return root; // 단말 노드일 경우

        Order left, right;
        int i = 0;
        while(true){
            if(subTree.pre.front() == subTree.in.front()) break; // 왼쪽 서브트리가 존재하지 않을 경우
            left.pre.push_back(subTree.pre[i+1]);
            left.in.push_back(subTree.in[i]);
            i++;
            if(subTree.in[i] == rootNode) break;
        }
        i++;
        while(i < subTree.pre.size()){
            right.pre.push_back(subTree.pre[i]);
            right.in.push_back(subTree.in[i]);
            i++;
        }

        root->left = makeTree(left);
        root->right = makeTree(right);

        return root;
    }
};

전위순회 결과를 통해 맨 앞의 노드가 전체 트리의 루트임을 알 수 있고 중위순회 결과에서 찾은 루트노드를 기준으로 왼쪽, 오른쪽 서브트리를 구분할 수 있다.

재귀 구조를 통해 계속해서 서브트리로 나누다보면 트리가 완성된다.

소스코드에 작성한 주석 부분(예외처리문)을 꼼꼼하게 생각해보지 않고 무작정 구현부터 시도하다가 디버깅에 많은 시간이 걸렸다.