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

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

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

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

假设我们这样做，我们推右 child ，推左 child ，然后才访问节点(有点镜像(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 的不是我们在将子节点插入堆栈之前访问了一个节点，而是在从堆栈中永久删除节点(因此在访问它之后)之后我们弹出(并因此访问)堆栈上的子节点。堆栈中的 child 最终在某个时候被弹出和访问，但他们的父已经被弹出和访问 - 因此这是预购。这种方法似乎是一个死胡同。

但还有另一种方式!我们可以通过颠倒 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 - 例如，如果我们跟踪最后访问的节点。