Simple and clean C++ solution


  • 0

    Recursive implementation where we just need to specify the index of the new root in postorder array:

        TreeNode* bt(vector<int>& in, vector<int>& post, int from, int to, int root) {
            for (int i = from; i <= to; ++i) {
                if (in[i] == post[root]) {
                    TreeNode* res = new TreeNode(in[i]);
                    res->left = bt(in, post, from, i - 1, root - to + i - 1);
                    res->right = bt(in, post, i + 1, to, root - 1);
                    return res;
                }
            }
            return NULL;
        }
        
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            int n = inorder.size();
            return bt(inorder, postorder, 0, n - 1, n - 1);
        }
    

Log in to reply
 

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