为什么 2 个堆栈对 post 阶横切如此有效

Question

所以我熟悉后序遍历：

L -> R -> P（从左到右到父级）。

我看到一个代码可以使用 2 个堆栈非常优雅地执行后序遍历：

public void postOrderTransverse(Node r){
    if(r == null){return;}
    Stack<Node> s = new Stack<Node>();
    Stack<Node> reverser = new Stack<Node>();
    s.push(r);
    while(!s.isEmpty()){
        Node temp = s.pop();
        reverser.push(temp);
        if (temp.left != null){
            s.push(temp.left);}
        if(temp.right != null){
            s.push(temp.right);}
    }
    while(!reverser.empty()){
        System.out.print(reverser.peek());
        reverser.pop();
    }
}

（通过 http://articles.leetcode.com/binary-tree-post-order-traversal/）

从本质上讲，一个 Stack 只是颠倒了另一个。我只是很好奇这是如何工作的。我有一个假设 Stack s 接受输入，这样输出就像 P -> R -> L，它只是将它传递给 Stack reverser，它吐出 L -> R .-> P，因为它是后进先出.

但是，只是想通过这个算法的过程来思考，我很难理解 Stack s 如何以及为什么按照它的方式接受输入。希望我能在这里有所了解！谢谢 :)

Answer 1

您提供的代码只是相应递归解决方案的循环版本：

public void postOrderTraverseRecursive(Node r){
    if(r == null){return;}

    if (r.left != null){
        postOrderTraverseRecursive(r.left);}
    if(r.right != null){
        postOrderTraverseRecursive(r.right);}

    System.out.print(r);
}

为了将递归转换为循环，我们需要 reverse the order of the statements execution。我们将使用一个堆栈来维护递归调用，并使用一个堆栈来维护递归的输出（即 System.out.print 语句参数）。

您的代码具有更有意义的变量名称和解释：

public void postOrderTraverse(Node root){
    if(root == null){return;}
    Stack<Node> recursionStack = new Stack<Node>();
    Stack<Node> printStack = new Stack<Node>();
    recursionStack.push(root);
    while(!recursionStack.isEmpty()){
        Node node = recursionStack.pop();
        /* Recursion iteration start */
        // According to the recursion we should process left->right->node.
        // Considering that in the loop version we have to reverse the order of invocations,
        // we are processing node->right->left
        printStack.push(node); // node is added to printStack immediately
        // left is added to recursionStack first, but because
        // of the FILO nature of the stack it will be processed last
        if (node.left != null){
            recursionStack.push(node.left);}
        // right is added to recursionStack last, but because
        // of the FILO nature of the stack it will be processed first
        if(node.right != null){
            recursionStack.push(node.right);}
        /* Recursion iteration end */
    }
    // We've processed all the input and now we have reversed
    // history of the prints, processing them in reverse order
    // to receive the actual one
    while(!printStack.empty()){
        System.out.print(printStack.peek());
        printStack.pop();
    }
}

为什么 2 个堆栈对 post 阶横切如此有效

why 2 stacks are so effective for post-order transverses

java

algorithm

binary-tree

postorder