使用一个堆栈的PostOrder遍历

Question

我正在尝试理解使用堆栈的DFS树遍历。我发现在将递归解决方案转换为迭代解决方案以进行预排序遍历时，这是非常直观的。然而，我发现使用这个链接很难理解postorder遍历。https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/。有没有一种直观而简单的方式来思考这个问题呢？预订码：

void iterativePreorder(node *root)
{
    // Base Case
    if (root == NULL)
       return;

    // Create an empty stack and push root to it
    stack<node *> nodeStack;
    nodeStack.push(root);

    /* Pop all items one by one. Do following for every popped item
       a) print it
       b) push its right child
       c) push its left child
    Note that right child is pushed first so that left is processed first */
    while (nodeStack.empty() == false)
    {
        // Pop the top item from stack and print it
        struct node *node = nodeStack.top();
        printf ("%d ", node->data);
        nodeStack.pop();

        // Push right and left children of the popped node to stack
        if (node->right)
            nodeStack.push(node->right);
        if (node->left)
            nodeStack.push(node->left);
    }
}

Answer 1

对于预订单遍历，代码

• 显示当前节点的数据
• 遍历左子树
• 遍历右子树

对于后序遍历，代码

• 遍历左子树
• 遍历右子树
• 显示当前节点的数据

因此，不同之处在于，在执行后序遍历时，数据需要存储在堆栈中，以便最后打印。有几种不同的方法可以做到这一点。一种方法是更改堆栈实现，以区分子指针和数据指针。

当子指针弹出时，操作为

• 将当前节点作为数据指针推送
• 将右侧节点作为子指针推送
• 将左节点作为子指针推送

当弹出数据指针时，操作为

• 显示节点

的数据

然后，通过将根节点作为子指针推入来开始遍历。

Answer 2

虽然代码比较难，但迭代后序可能比其他遍历更直观，因为其他遍历已经重构，而这个不能进行类似的重构。

这里使用第一个解决方案：https://articles.leetcode.com/binary-tree-post-order-traversal/

直觉是递归函数具有迭代方法没有的信息，主要是遍历方向。当递归函数执行或回退时，它知道它是从哪一行代码中来的。如果你正在打印或处理当前节点，你知道你已经访问了子节点，因为它们已经被递归调用了。

迭代解决方案可以通过使用“上一个”指针来跟踪它，因此你会看到“如果前一个不是当前节点的任何一个子节点”的检查，那么这意味着你正在向下遍历，你需要向左移动。其他可能性是前一个来自左侧或右侧的子节点。一旦所有的案例都被处理了，你就有了解决方案。

Answer 3

请在下面找到使用java中的一个堆栈进行PostOrder遍历的代码片段

public class PostOrderWithoutRecurssion {

    static Stack<Node> stack = new Stack<Node>();

    static class Node{
        int data;
        int status;
        Node left, right;

        Node(int data){
            this.data = data;
            this.status=0;
        }
    }//end class Node

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.left.left.left = new Node(8);
        root.left.left.right = new Node(9);

        postOrderWithoutRecurssion(root);
    }//end main

    public static void postOrderWithoutRecurssion(Node root) {
        Node temp = root;

        while(temp!=null || stack.size()>0) {

            while(temp!=null) {
                temp.status = 1;
                stack.push(temp);
                temp = temp.left;
            }

            temp = stack.pop();

            if(null==temp.left && null == temp.right) {
                temp.status = 2;
                System.out.println(temp.data);
            }else if(null != temp.right) {
                if(temp.left.status==2 && temp.right.status==2) {
                    temp.status = 2;
                    System.out.println(temp.data);
                    temp = null;
                }else {
                    if(temp.status!=1) {
                        temp.status = 1;
                        stack.push(temp);
                    }else {
                        stack.push(temp);
                    }
                }
            }

            if(null!=temp) {
                temp = temp.right;    
            }

        }
    }//end postOrderWithoutRecurssion
}