Share my code, use hash and recursion. Beat 90%.


  • 0
    O
    class Solution {
    private:
        unordered_map<int, int> indexMap;
    public:
        TreeNode* constructTree(vector<int>& inorder, int in_begin, int in_end,
                                vector<int>& postorder, int ps_begin, int ps_end) {
            if (in_begin > in_end || ps_begin > ps_end)
                return nullptr;
                
            TreeNode* root = new TreeNode(postorder[ps_end]);
            if (in_begin == in_end)
                return root;
            int rootIndex = indexMap[postorder[ps_end]];
            int leftLen = rootIndex - in_begin;
            root->left = constructTree(inorder, in_begin, rootIndex - 1, 
                                       postorder, ps_begin, ps_begin + leftLen - 1);
            root->right = constructTree(inorder, rootIndex + 1, in_end, 
                                       postorder, ps_begin + leftLen, ps_end - 1);
            
            return root;
        }
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            for (int i = 0; i < inorder.size(); i++)
                indexMap[inorder[i]] = i;
            return constructTree(inorder, 0, inorder.size() - 1, 
                                 postorder, 0, postorder.size() - 1);
        }
    };

Log in to reply
 

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