19ms C++ solution


  • 1
    S
    /**
     * 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 {
    public:
        TreeNode* getRoot(vector<int>& in, int l1, int r1, vector<int>& post, int l2, int r2){
            if(l1>r1 || l2>r2){
                return NULL;
            }
            TreeNode* root = new TreeNode(post[r2]);
            if(l1==r1){
                return root;
            }
            int val = root->val;
            int i=l1;
            for(i=l1;i<=r1;i++){
                if(in[i]==val){
                    break;
                }
            }
            i--;
            root->left=getRoot(in,l1,i,post,l2,l2+i-l1);
            root->right=getRoot(in,i+2,r1,post,r2-(r1-i-2+1),r2-1);
            return root;
        }
        TreeNode* buildTree(vector<int>& in, vector<int>& post) {
            if(post.size()==0){
                return NULL;
            }
            return getRoot(in,0,in.size()-1,post,0,post.size()-1);
        }
    };
    

Log in to reply
 

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