理解二叉树上迭代后序遍历实现的逻辑

Question

我试图理解使用 2 个堆栈实现后序遍历是多么直观。有人是如何想出它的，它只是一种观察或某种特定的思维方式，可以帮助人们想出这样的方法。如果是，那么请解释如何朝着正确的方向思考。

Answer 1

让我解释一下我是如何偶然发现解决方案的：

你从这个简单的观察开始：表面上看，前序遍历和后序遍历仅在它们的操作顺序上不同：

preOrder(node):
    if(node == null){
         return
    }
    visit(node)
    preOrder(node.leftChild)
    preOrder(node.rightChild)

postOrder(node):
    if(node == null){
         return
    }
    postOrder(node.leftChild)
    postOrder(node.rightChild)
    visit node

preOrder 函数执行一些计算（访问节点）和对自身的两次递归调用 - 让我们将此订单称为“VLR”。postOrder 函数进行两次递归调用，然后访问节点（'LRV'）。

preOrder 适合一个简单的迭代实现，我们访问节点，并将与递归调用相对应的计算推送到堆栈上。

    var nodeStack = new Stack();
    nodeStack.push(this.root())
    while(!nodeStack.isEmpty()){
        var currentNode = nodeStack.pop();
        visit(currentNode);
        if (currentNode.rightChild){
            nodeStack.push(currentNode.rightChild)
        }

        if (currentNode.leftChild){
            nodeStack.push(currentNode.leftChild)
        }
    }

堆栈包含未访问节点的列表。我们弹出一个节点，访问它，推动它的右孩子，推动左孩子。重复。这给了我们预购。

（注意：对于 VLR，我们在左孩子之前推送右孩子，因为堆栈是 LIFO - 我们在访问之前推送的孩子之前访问最后推送的孩子 - 我们希望在右孩子之前访问左孩子。对于VRL，我们将不得不改变顺序）

假设我们这样做，我们推右孩子，推左孩子，然后才访问节点（有点镜像（1）递归调用和（2）节点访问的相对顺序 postOrder。我们尝试使 VLR 到 LRV通过在最后移动 V）。

    var nodeStack = new Stack();
    nodeStack.push(this.root())
    while(!nodeStack.isEmpty()){
        var currentNode = nodeStack.pop();
        if (currentNode.rightChild){
            nodeStack.push(currentNode.rightChild)
        }

        if (currentNode.leftChild){
            nodeStack.push(currentNode.leftChild)
        }
        visit(currentNode);
    }   

这应该给我们 postOrder 吧？不，这仍然是预购。定义 preOrder 的不是我们在将子节点推入堆栈之前访问了一个节点，而是在从堆栈中永久删除节点（因此在访问它之后）之后我们弹出（并因此访问）堆栈上的子节点。堆栈中的孩子最终在某个时候被弹出和访问，但他们的父已经被弹出和访问 - 因此这是预购。这种方法似乎是一个死胡同。

但还有另一种方式！我们可以通过颠倒 VLR 中 L 和 R 的顺序（使其成为 VRL），然后将生成的 'VRL' 颠倒为使其成为“LRV”。

从左到右后序遍历 (LRV) 生成的序列与“VRL”的逆序相同——由从右到左前序遍历生成的序列。

让我们通过使其 VRL 来调整我们的迭代 preOrder：

    var nodeStack = new Stack();
    nodeStack.push(this.root())
    while(!nodeStack.isEmpty()){
        var currentNode = nodeStack.pop();

        if (currentNode.leftChild){
            nodeStack.push(currentNode.leftChild)
        }

        if (currentNode.rightChild){
            nodeStack.push(currentNode.rightChild)
        }

        visit(currentNode);
    }   

这将给我们一个 VRL preOrder（一个序列，其反向是 LRV，postOrder）。我们只需要逆向遍历即可！这就是需要第二个堆栈的地方。如果我们将我们访问的每个节点推送到另一个堆栈，然后从上到下遍历它，我们将获得我们的 postOrder！

这是我的最终解决方案：

    var reverseStack = new Stack();
        while(!nodeStack.isEmpty()){
            var currentNode = nodeStack.pop()
            reverseStack.push(currentNode)
            if (currentNode.leftChild){
                nodeStack.push(currentNode.leftChild)
            }

            if (currentNode.rightChild){
                nodeStack.push(currentNode.rightChild)
            }
        }

        while(!reverseStack.isEmpty()){
            console.log(reverseStack.pop().getElement())
        }

您可以进行一些小的优化 - 这将为您提供您在网上看到的标准两个堆栈解决方案。请注意，两个堆栈不是必需的 - 并且可以只用一个堆栈实现 postOrder - 例如，如果我们跟踪最后访问的节点。