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

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

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode

 

두 개의 정수 배열인 preorder, inorder(전위, 중위 순회)을 이용해서 이진 트리를 구성하여 반환하는 문제이다.

 

나의 생각은 일단 중위 순회를  먼저 root 기준으로 반으로 나누고, 해당 leftNode와, rightNode를 만들어, 이를 순회하여 해당 트리를 완성하는 것이다.

 

/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        if (preorder.empty() || inorder.empty()) {
            return nullptr;
        }

        TreeNode* root = new TreeNode(preorder[0]);
        auto it = find(inorder.begin(), inorder.end(), preorder[0]);
        vector<int> front_part(inorder.begin(), it);
        vector<int> back_part(it + 1, inorder.end());

        Search(root, preorder, 0, front_part, back_part);

        return root;
    }
    void Search(TreeNode* root, vector<int>& preorder, int index, vector<int>& front_part, vector<int>& back_part)
    {
        if (index >= preorder.size() || (front_part.empty() && back_part.empty()))
            return;

        if (!front_part.empty())
        {
            int leftRootVal = preorder[index + 1];
            root->left = new TreeNode(leftRootVal);

            auto it = find(front_part.begin(), front_part.end(), leftRootVal);
            vector<int> next_front(front_part.begin(), it);
            vector<int> next_back(it + 1, front_part.end());

            Search(root->left, preorder, index + 1, next_front, next_back);
        }

        if (!back_part.empty())
        {
            int rightRootDepth = index + front_part.size() + 1;
            
            if (rightRootDepth < preorder.size()) 
            {
                int rightRootVal = preorder[rightRootDepth];
                root->right = new TreeNode(rightRootVal);

                auto it = find(back_part.begin(), back_part.end(), rightRootVal);
                vector<int> next_front(back_part.begin(), it);
                vector<int> next_back(it + 1, back_part.end());

                Search(root->right, preorder, rightRootDepth, next_front, next_back);
            }
        }
    }
};

해당 코드에서 왼쪽 노드들을 전부 검사하고, right를 검사하는 플로우다.