algorithm - ウィキペディアの反復的なポストオーダー ツリー トラバーサルの疑似コードは間違っていますか?

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 で null かどうかを確認するコードを追加する必要があります。