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[]} inorder
     * @param {number[]} postorder
     * @return {TreeNode}
     */
    var buildTree = function(inorder, postorder) {
        if (!inorder || inorder.length === 0 || !postorder || postorder.length === 0 || inorder.length !== postorder.length) {
            return null;
        }
        
        let hash = {};
        for (let i = 0; i < inorder.length; i++) {
            hash[inorder[i]] = i;
        }
        
        return helper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, hash);
    };
    
    var helper = function(inorder, is, ie, postorder, ps, pe, hash) {
        if (is > ie || ps > pe) { return null; }
        
        let root = new TreeNode(postorder[pe]);
        let ri = hash[postorder[pe]];
        let left = helper(inorder, is, ri - 1, postorder, ps, ps + ri - is - 1, hash);
        let right = helper(inorder, ri + 1, ie, postorder, ps + ri - is, pe - 1, hash);
        root.left = left;
        root.right = right;
        
        return root;
    };
    

Log in to reply
 

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