Less than 10 lines, neat c++ code!


  • 7
    P
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return builTreeHelper(preorder,0,preorder.size(),inorder,0,inorder.size());
    }
    
    TreeNode* builTreeHelper(vector<int>& preorder, int sp, int ep, vector<int>& inorder, int si, int ei) {
        if (sp == ep) return nullptr;
        TreeNode* root = new TreeNode(preorder[sp]);
        int dis = find(inorder.begin()+si,inorder.begin()+ei,preorder[sp]) - inorder.begin() - si;
        root->left = builTreeHelper(preorder,sp+1,sp+1+dis,inorder,si,si+dis);
        root->right = builTreeHelper(preorder,sp+1+dis,ep,inorder,si+dis+1,ei);
        return root;
    }

  • 0
    L

    Without helper function

        TreeNode* buildTree(vector<int> preorder, vector<int> inorder) {
            if(inorder.empty()||preorder.empty()) return NULL;
            int i = find(inorder.begin(), inorder.end(), preorder[0]) - inorder.begin();
            TreeNode* root = new TreeNode(preorder[0]);
            root->left = buildTree( vector<int>(preorder.begin()+1, preorder.begin()+i+1),
                                                    vector<int>(inorder.begin(), inorder.begin()+i) );
            root->right= buildTree( vector<int>(preorder.begin()+i+1, preorder.end()),
                                                    vector<int>(inorder.begin()+i+1, inorder.end()) );
            return root;
        }
    

Log in to reply
 

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