- это википедия, итеративный постер дерева обход псевдо-кода неправильно?

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.А, хотя.