JavaScript solution using stack


  • 0
    D
    
    /**
     * 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.length){
            return null;
        }
        
        let stack = [];
        
        let treeArr = [];
        let root = new TreeNode(preorder[0]);
        
        stack.push(root);
        
        for(let i = 1; i < preorder.length; i++){
            let node = new TreeNode(preorder[i]);
                        
            let peek = stack[stack.length - 1];
            let lastpeek = null;
            for(let j = 0; j < inorder.length; j++){
                peek = stack[stack.length - 1];
                
                if(inorder[j] == preorder[i]){
                    if(lastpeek){
                        // right node
                        lastpeek.right = node;
                    }
                    else
                    {
                        // left node
                        peek.left = node;
                    }
                    
                    stack.push(node);
                    break;
                }
                else if(peek && inorder[j] == peek.val){
                    lastpeek = stack.pop();
                }
                
            }
        }
    
        return root;
    };
    
    
    
    
    
    
    

Log in to reply
 

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