Javascript solution using recursion


  • 0
    S
    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {number[]} preorder
     * @param {number[]} inorder
     * @return {TreeNode}
     */
    var buildTree = function(preorder, inorder) {
        if (!preorder || !inorder || preorder.length !== inorder.length) { return null; }
        
        let hash = {};
        for (let i = 0; i < inorder.length; i++) {
            hash[inorder[i]] = i;
        }
    
        return helper(inorder, 0, inorder.length - 1, preorder, 0, preorder.length - 1, hash);
    };
    
    var helper = function(inorder, is, ie, preorder, ps, pe, hash) {
        if (ps > pe || is > ie) { return null; }
        
        let root = new TreeNode(preorder[ps]);
        let ri = hash[preorder[ps]];
        root.left = helper(inorder, is, ri - 1, preorder, ps + 1, ps + ri - is, hash);
        root.right = helper(inorder, ri + 1, ie, preorder, ps + ri - is + 1, pe, hash);
        
        return root;
    }
    

Log in to reply
 

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