C++ simple recursive solution


  • 0
    X
    class Solution {
    public:
        int find(const int val, const int l, const int r, const vector<int>& vec) const{
            for(int i = l;i <= r; ++i){
                if(vec[i] == val){
                    return i;
                }
            }
            return -1;
        }
        TreeNode* build(int pl, int pr, int il, int ir, vector<int>& preorder, vector<int>& inorder){
            if(pl > pr){
                return NULL;
            }else if(pl == pr){
                return new TreeNode(preorder[pl]);
            }
            int p = find(preorder[pl], il, ir, inorder);
            TreeNode* root = new TreeNode(preorder[pl]);
            root->left = build(pl + 1, pl + p - il, il, p - 1, preorder, inorder);
            root->right = build(pl + p - il + 1, pr, p + 1, ir, preorder, inorder);
            return root;
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            if(preorder.empty()){
                return NULL;
            }
            return build(0, preorder.size() - 1, 0, inorder.size() - 1, preorder, inorder);
        }
    };

Log in to reply
 

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