pathSum with Stack in JavaScript


  • 0
    N
    const Stack = function() {
        this._storage = {};
        this._index = 0;
    };
    
    Stack.prototype.push = function(value) {
        this._storage[++this._index] = value;
    };
    
    Stack.prototype.pop = function() {
        if(this.length()) {
            let removed = this._storage[this._index];
            delete this._storage[this._index--];
            return removed;
        }
    };
    
    Stack.prototype.length = function() {
        return this._index;
    };
    
    Stack.prototype.toArray = function() {
        let output = [];
        
        for(let i = 1; i <= this._index; i += 1) {
            output.push(this._storage[i]);
        }
        
        return output;
    };
    
    
    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @param {number} sum
     * @return {number[][]}
     */
    const pathSum = function(root, sum) {
        if(!root) {
            return [];
        }
     
        const recursion = (root, sum, stack, result) => {
            stack.push(root.val);
            
            if(root.left === null && root.right === null && root.val === sum) {
                result.push(stack.toArray());
            }
            
            if (root.left !== null) {
                recursion(root.left, sum - root.val, stack, result);
            }
            
            if (root.right !== null) {
                recursion(root.right, sum - root.val, stack, result);
            }
            
            stack.pop(root.val);
        };
          
        let response = [];
        let stack = new Stack();
        
        recursion(root, sum, stack, response);
        
        return response;
    };
    

Log in to reply
 

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