Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

Medium

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

Construct Binary Tree from Inorder and Postorder Traversal - LeetCode

 

language: C++

출처: References 참고

time: O(N)

/**
 * 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>& inorder, vector<int>& postorder) {
    
        int pIndex = postorder.size() - 1;
        TreeNode* root = buildUtil(inorder, postorder, 0, inorder.size() - 1, &pIndex);
        return root;
    }
    
    TreeNode* buildUtil(vector<int>& inorder, vector<int>& postorder, int left,
                int right, int* postorderIdx)
    {
        // Base case
        if (left > right)
            return NULL;

        /* Pick current node from Postorder traversal using
           postIndex and decrement postIndex */
        TreeNode* node = new TreeNode(postorder[*postorderIdx]);
        (*postorderIdx)--;

        /* If this node has no children then return */
        if (left == right)
            return node;

        /* Else find the index of this node in Inorder
           traversal */
        int i;
        for (i = left; i <= right; i++) {
            if (inorder[i] == node->val)
                break;
        }
        int iIndex = i;

        /* Using index in Inorder traversal, construct left and
           right subtress */
        node->right = buildUtil(inorder, postorder, i + 1, right, postorderIdx);
        node->left = buildUtil(inorder, postorder, left, i - 1, postorderIdx);

        return node;
    }
    
    
};

내가 원하는 답변

class Solution {
public:
    TreeNode* helper(vector<int>& inorder, vector<int>& postorder, int& rootIdx, int left, int right){
        if (left > right) return nullptr;
        int pivot = left;
        while (inorder[pivot] != postorder[rootIdx]) pivot++;
        
        rootIdx--;
        
        TreeNode * newnode = new TreeNode(inorder[pivot]);
        newnode -> right = helper(inorder, postorder, rootIdx, pivot +1, right);
        newnode -> left = helper(inorder, postorder, rootIdx, left, pivot -1);
        
        return newnode;
    }
    
    
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int rootIdx = postorder.size() - 1;
        return helper(inorder, postorder, rootIdx, 0, inorder.size() - 1);
    }
};

내가 구현하길 원한 건 위의 코드 같은 거였다....;

시도

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        
        return helper(inorder, postorder, 0, inorder.size() - 1, postorder.size() - 1);
        
    }

TreeNode* helper(vector<int>& inorder, vector<int>& postorder, int left, int right, int postorderIdx) {
        if (left > right)
            return nullptr;
        else if(left == right) {
            TreeNode* result = new TreeNode(inorder[left]);
            return result;
        } else {
            // find root
            // int i = left;
            // while(i <= right && inorder[i] != postorder[postorderIdx])
            //     i++;
            bool find = false;
            int i = left;
            for(i = left; i <= right; i++) {
                if (inorder[i] == postorder[postorderIdx]) {
                    find = true;
                    break;
                }
            }
            int value = postorder[postorderIdx];
            if (!find) {
                value = postorder[postorderIdx - 1];
                
                for(i = left; i <= right; i++) {
                    if (inorder[i] == value) {
                        break;
                    }
                }
            }

            TreeNode* result = new TreeNode(value);
            result->right = helper(inorder, postorder, i + 1, right, postorderIdx - 1);
            result->left = helper(inorder, postorder, left, i - 1, postorderIdx - 1);

            return result;
        }
    }

문제점

처음에 inorder랑 postorder 비교해서 여러 개 가능한 트리를 뽑고 비교해야되나? 생각했었는데 그건 전혀 아니었고

솔루션 설명을 보고 혼자 짜보았는데 postorder 를 하나씩 pop 하길래 c++ 그렇게 굳이 해야되나 인덱스를 어차피 넘겨주는데? 라고 생각하고 제대로 넘겨주면 되겠지 하면서 계속 했는데 자꾸 테케에서 걸렸다.

첫번째는 left, right 의 index 가 같은 경우를 고려하지 못했고 그래서 무한루프 떴었다 -> 같은 경우 현재 inorder[left] 로 변경했는데 해당 케이스는 통과했으나 다른 테케에서 문제 발생

두 번째는 postorderIdx 에 해당하는 값이 left, right 범위에 없을 경우였는데 그때는 postorder[postorderIdx - 1] 로 대체했었는데 이것도 다른 테케에서 문제 발생 -> 그래서 구글링해서 찾은 소스에는 그냥 val을 무조건 postorder[postorderIdx] 으로 넣어주길래 이해안됐다.

세번째는 postorderIdx 를 주소값으로 전달해주면서 끌고다녔던 점이 달랐다. 끌고 다녔어야 했는데 그걸 생각 못했다.

=> postorderIdx 가 트리의 level 이라고 생각이 되기도 했는데 그렇다기 보다는, 

postorderIndex 는 postorder 을 뒤에서부터 가리키면서 가는 것이고, output 배열에 넣는 대상을 가리키는 것이다. 리트코드에 있는 솔루션 그림을 보면 이해가 바로 될텐데 첨부하긴 조심스럽다;; 

=> node->right 하고 node->left 하는 건 postorder(LRV) 의 뒤에서부터 하니까 순서를 뒤집어서 그렇게 한 것(VRL)..

뭔가 솔루션에서 힌트를 얻어서 접근해본 것은 전체적인 구조는 비슷했는데 비슷하긴만 하지 맞은 건 아니라서 머리 쥐어 뜯으면서 했는데

보니까 난이도가 Medium 이었다? 문제만 봤을 때는 안 어려운 문제 같은데;; 파이썬으로 짠 것은 매우 쉬워보이더라

갈길이 너무 멀다 답답하다 머리 다 빠질 것 같다 화나서 다른 문제도 더 풀고 싶은데 걍 집가야지

 

References

https://www.geeksforgeeks.org/construct-a-binary-tree-from-postorder-and-inorder/

Construct a Binary Tree from Postorder and Inorder - GeeksforGeeks

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/discuss/1289210/Easy-C%2B%2B-solution-using-recursion-using-binary-tree-from-Preorder-and-Inorder-Traversal.