Simple C++ Solution (13ms beats 95%)


  • 0
    G
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            unordered_map<int, int> inorder_map;
            for (int i = 0; i < inorder.size(); i++) inorder_map[inorder[i]] = i;   // to help quick lookup in 'inorder'
            
            return _buildTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, inorder_map);
        }
        TreeNode* _buildTree(vector<int>& inorder, int in_start, int in_end,
                             vector<int>& postorder, int po_start, int po_end,
                             unordered_map<int, int>& inorder_map) {
            if (po_start > po_end) return NULL;
            
            TreeNode* root = new TreeNode(postorder[po_end]);
            int inorder_idx = inorder_map[postorder[po_end]];
            int left_size = inorder_idx - in_start;
            
            root->left = _buildTree(inorder, in_start, in_start + left_size - 1,
                                    postorder, po_start, po_start + left_size - 1,
                                    inorder_map);
            root->right = _buildTree(inorder, inorder_idx + 1, in_end,
                                     postorder, po_start + left_size, po_end - 1,
                                     inorder_map);
            
            return root;
        }
    

Log in to reply
 

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