8-liner using iterator

  • 0

    Find the root value from preorder and check its inorder's position, and then process left and right subtrees recursively.

        typedef vector<int>::iterator Itr;
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            auto p = preorder.begin();
            return dfs(p, inorder.begin(), inorder.end());
        // p: preorder start; i1: inorder start; i2: inorder end
        TreeNode* dfs(Itr &p, Itr i1, Itr i2) {
            if (i1 == i2) return nullptr;                
            auto i = find(i1, i2, *p);
            auto r = new TreeNode(*p++);
            r->left  = dfs(p, i1, i); 
            r->right = dfs(p, ++i, i2);
            return r;

Log in to reply

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