0

这是维基百科为迭代后序树遍历提供的伪代码。

iterativePostorder(node)
  parentStack = empty stack  
  lastnodevisited = null 
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)
      parentStack.push(node)
      node = node.left
    else
      peeknode = parentStack.peek()
      if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right) 
        /* if right child exists AND traversing node from left child, move right */
        node = peeknode.right
      else
        visit(peeknode)
        lastnodevisited = parentStack.pop()

这很简单，我已经用 Java 实现了它。但它不起作用，问题是每次它访问最左边的叶子并返回其父级时，它会在下一次迭代中再次将左边的叶子添加到堆栈中。这会导致无限循环。我的方法不正确还是维基百科版本错误？

public static List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    if (root == null) return res;
    Stack<TreeNode> s = new Stack<TreeNode>();
    TreeNode lastVisitedNode = null;
    TreeNode curr = root;
    int i = 0;
    while (curr != null || !s.isEmpty()) {
        if (curr != null) {
            System.out.println("push " + curr.val);
            s.push(curr);
            curr = curr.left;
        } else {
            curr = s.peek();
            if (curr.right != null && lastVisitedNode != curr.right) {
                curr = curr.right;
            } else {
                res.add(curr.val);
                System.out.println("pop " + curr.val);
                lastVisitedNode = s.pop();
            }
        }
        System.out.println(s);
        System.out.println(res);
        if (i>8) break;
        else i++;
    }
    return res;
}
4

2 回答 2

0

由于与您解释的完全相同的原因，维基百科版本是错误的。

这是一个可能更好的伪代码，来自geeksforgeeks

1.1 Create an empty stack
2.1 Do following while root is not NULL
    a) Push root's right child and then root to stack.
    b) Set root as root's left child.
2.2 Pop an item from stack and set it as root.
    a) If the popped item has a right child and the right child 
       is at top of stack, then remove the right child from stack,
       push the root back and set root as root's right child.
    b) Else print root's data and set root as NULL.
2.3 Repeat steps 2.1 and 2.2 while stack is not empty.

您将不得不添加额外的代码来检查节点右子节点在 2.1.a 中是否为空。

于 2014-11-14T22:29:38.957 回答
0

维基百科的伪代码没有错。它们使用两个不同的变量：node和peekNode，而您只curr用于两者。Node == null指的是没有更多左分支可供探索的情况，因此我们可以停止推送，而是调查堆栈中的下一个元素。您可以恢复使用两个不同的变量，也可以在代码中进行以下修复：

由于curr每次调查堆栈时都会重新分配一个非空值，因此您需要curr在访问节点后重置为空值。（因为仍然没有左分支可以探索的状态仍然没有改变）。

维基百科伪代码不必这样做，因为它们的node值仍然为空。

这是我的代码，它给出了一个完美的答案：

var currentNode = this.root()
var previousNode = null
while(!nodeStack.isEmpty() || currentNode) {

    // If there is a node on which the recursive call is made, we have a subtree to explore. If this is null, we have to backtrack and do a callback. 
    if (currentNode) {
        nodeStack.push(currentNode)
        previousNode = currentNode
        currentNode = currentNode.leftChild
    } else {
        currentNode = nodeStack.peek()
        if (currentNode.rightChild && previousNode != currentNode.rightChild) {
            currentNode = currentNode.rightChild    
        } else {
            callback(currentNode)
            currentNode = null
            previousNode = nodeStack.pop()
        }
    } 
}
于 2018-05-31T15:16:25.160 回答