Sharing my 40ms C++ solution


  • 0
    T
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    private:
        TreeNode* buildTreeHelper(vector<int>& inorder, vector<int>& postorder, int inf, int inl, int pof, int pol)
        {
            if(pof>pol)
                return NULL;
            TreeNode* tree = new TreeNode(postorder[pol]);
            int midvalue = postorder[pol];
            int shift;
            int i;
            for(i=0; i<=inl-inf; i++)
            {
                if(inorder[inf+i] == midvalue)
                {
                    shift = i;
                    break;
                }
            }
            
            tree->left = buildTreeHelper(inorder, postorder, inf, inf+shift-1, pof, pof+shift-1);
            tree->right = buildTreeHelper(inorder, postorder, inf+shift+1, inl, pof+shift, pol-1);
            return tree;
        }
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            int ni = inorder.size();
            int np = postorder.size();
            return buildTreeHelper(inorder, postorder, 0, ni-1, 0, np-1);
        }
    };

Log in to reply
 

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