0

所以我熟悉后序遍历：

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 s 接受输入，因此输出类似于 P -> R -> L，它只是将其传递给 Stack reverser，后者吐出 L -> R .-> P，因为它是后进先出.

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

4

1 回答 1

2

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

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);
}

为了将递归转换为循环，我们需要颠倒语句执行的顺序。我们将使用一个堆栈来维护递归调用，并使用一个堆栈来维护递归的输出（即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();
    }
}
于 2016-08-19T05:40:46.333 回答