Construct Binary Tree from Preorder and Inorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal

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

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode

 

language: C++

class Solution {
public:
    TreeNode *buildTree(vector<int>& pre, vector<int>& in) {
        return helper(pre, in, 0, pre.size()-1, 0, in.size()-1);
    }
    TreeNode *helper(vector<int>& pre, vector<int>& in, int ps, int pe, int is, int ie) {
        if(is > ie) return nullptr;
        
        TreeNode *root = new TreeNode(pre[ps]);
        int pos;
        for(int i = is; i < ie; i++)
            if(in[i] == root->val) {
                pos = i;
                break;
            }
        
        // pe-ps = ie-is
        // pe = ps+ie-is
        // now all should correspond to left part
        // pe = (ps+1)+(pos-1)-(is) = ps+pos-is
        root->left = helper(pre, in, ps+1, ps+pos-is, is, pos-1);
        root->right = helper(pre, in, ps+pos-is+1, pe, pos+1, ie);
        
        return root;
    }

class Solution {
public:
    TreeNode* create(vector<int>&p,vector<int>&i,int l,int h,int k)
    {
        if(l>h)
            return nullptr;
        int j;
        for(j=l;j<=h;j++)
            if(p[k]==i[j])
                break;
        TreeNode* root=new TreeNode(p[k]);
        root->left=create(p,i,l,j-1,k+1);
        root->right=create(p,i,j+1,h,k+j-l+1);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return create(preorder,inorder,0,inorder.size()-1,0);
    }
};

솔루션 참고 후 수정

/**
 * 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[0] == -1 && inorder[0] == -1)
            return new TreeNode(-1);
        
        return helper(preorder, inorder, 0, inorder.size() - 1, 0, preorder.size() - 1);
    }
    
    TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int left, int right, int ps, int pe) {
        
        if (left > right)
            return nullptr;
        
        if(ps >= preorder.size())
            return nullptr;
        
        TreeNode* node = new TreeNode(preorder[ps]);
        
        if (left == right)
            return node;
        
        int i;
        for (i = left; i <= right; i++) {
            if (inorder[i] == node->val)
                break;
        }
        
        node->left = helper(preorder, inorder, left, i - 1, ps + 1, ps + i - left);
        node->right = helper(preorder, inorder, i + 1, right, ps + i - left + 1, pe);
        
        return node;
    }
};

 

시도

/**
 * 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) {
        int preorderIdx = 0;
        
        if (preorder[0] == -1 && inorder[0] == -1)
            return new TreeNode(-1);
        
        return helper(preorder, inorder, 0, inorder.size() - 1, preorderIdx);
    }
    
    TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int left, int right, int preorderIdx) {
        
        if (left > right)
            return nullptr;
        
        if(preorderIdx >= preorder.size())
            return nullptr;
        
        TreeNode* node = new TreeNode(preorder[preorderIdx]);
        // (*preorderIdx)++;
        
        
        if (left == right)
            return node;
        
        //search
        int i;
        for (i = left; i <= right; i++) {
            if (inorder[i] == node->val)
                break;
        }
        
        node->left = helper(preorder, inorder, left, i - 1, preorderIdx + 1);
        node->right = helper(preorder, inorder, i + 1, right, preorderIdx + 2);
        
        
        return node;
    }
};

failed test case

pre: [1, 2]

in: [1, 2]

output: [1]

answer: [1, null 2] 

 

문제점

어제 input이 postorder, inorder 으로 주어진 것을 풀었기에 루트를 먼저 찾았고, 

preorder 의 경우 VLR 순서이기에 맨 처음 원소가 root 이라는 것을 발견, 어제랑 비슷한 방식으로 recursion 으로 풀려고 시도, 

그런데 풀다보니까 preorder 배열을 위한 start, end index 가 필요하다는 생각이 들었다. 그런데 확신이 들지 않고 뭉뚱그려지기만 해서 생각해보다가 솔루션을 보았다.

솔루션은 python, java 로 되어있고 자꾸 map 을 써서 나는 그게 싫어서 댓글에 있는 다른 솔루션 찾았고,

preorder 에 대한 start, end index를 전달해주는 게 맞았었다.

왜냐하면 preorder VLR 순서이기에 루트 이후에 좌측 서브트리 원소들 이후 우측 서브트리 원소들이라

좌측 서브트리 원소들의 개수 만큼을 지나쳐야 우측 서브트리 원소가 시작되기 때문에 

ps + i - left       

// + (i - left) => (좌측 원소 서브트리 원소들의 개수) 인데 -left 를 해주는 이유가 현재 서브트리의 루트라고 알게되는 원소를 찾기 시작하는 left 를 빼줘야 현재 레벨에 해당하는 좌측트리 범위라고 볼 수 있는 것임..

=> 이렇게 설명을 할 줄 알아야 되는데 설명도 못하겠고 긴가민가 해서 (뭉뚱그려지기만 하다는 것) 시도를 안해봤다.

해주고 우측 서브트리의 시작은 여기서 +1 을 해주면 된다.

// 이것도 확실히 생각을 못했다. 그냥 돌려보고 안되서 솔루션을 다시보고 +1 추가했음;

설명을 할 수 있도록 명확하게 생각이 그려지기 보다는 긴가민가 뭉뚱그려지는 것들을 시도해보지 않았던 것이 오늘 문제를 접근한 방식 중 아쉬운 점 같다.

preorder start, end index 의 생각을 지워버렸던 또 다른 한 가지의 이유가 변수 하나로도 할 수 있을 거라고 생각 했었는데 

그대로 구현된 게 현재 포스팅의 두 번째 코드블럭이다. 이렇게 하고 싶었던 거였지....

런타임 속도가 빠른 해답들은 map을 쓰더라.. 이해하기 싫어서 넘어갔다.. 아직은 무리라고 생각되서ㅠㅠㅠ 조금씩 하려구요...ㅎㅎ