postOrderTraversal iteratively with 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.size()) {
            let removed = this._storage[this._index];
            delete this._storage[this._index--];
            return removed;
        }
    };
    
    Stack.prototype.size = function() {
        return this._index;
    };
    
    
    /**
     * Definition for a binary tree node.
     * function TreeNode(val) {
     *     this.val = val;
     *     this.left = this.right = null;
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {number[]}
     */
    const postorderTraversal = function(root) {
        let response = [];
        
        if(!root) {
            return response;
        }
        
        let bufferStack = new Stack();
        let postOrderStack = new Stack();
        
        bufferStack.push(root);
        
        // left, right, root - post-order
        while(bufferStack.size()) {
            let node = bufferStack.pop();   
            
            if(node.left) {
                bufferStack.push(node.left);
            }
            
            if(node.right) {
                bufferStack.push(node.right);
            }
            
            postOrderStack.push(node.val);
        }
        
        while(postOrderStack.size()) {
            response.push(postOrderStack.pop());
        }
        
        return response;
    };
    

Log in to reply
 

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