是維基百科迭代後序樹遍歷僞代碼錯誤？

Question

這是維基百科爲迭代後序樹遍歷提供的僞代碼。

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

Answer 1

維基百科的版本是錯了，你已經解釋了它的確切同樣的原因。

這裏是一個可能是更好的僞代碼，從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空雖然。