C++ code using map


  • 0
    X
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            map<int,int> table;
            for(auto i=0; i!= inorder.size(); i++) table[inorder[i]] = i;
            return makeTree(postorder, 0, postorder.size()-1, 0, table);
        }
    
    private:
    
        TreeNode* makeTree(vector<int>& postorder, int front, int back, int mark, map<int,int> &table) { 
            if(front > back) return NULL;
            int target = preorder[back];
            int pos = table[target];
            TreeNode* node = new TreeNode(target);
            node->left = makeTree(postorder, front, front + pos - mark - 1,  mark, table);
            node->right = makeTree(postorder, front + pos - mark, back-1,  pos + 1, table);
            return node;
        }
    };
    

    This piece is inspired by iAlan's preorder/inorder build tree solution


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.