pourquoi 2 piles sont si efficaces pour postorder Transverses

Question

Je suis au courant de postorder traversant:

L -> R -> P (De gauche à droite au parent).

je vis un code qui pourrait effectuer une traversal postorder tout en utilisant élégamment 2 piles:

public void postOrderTransverse(Node r){ 
    if(r == null){return;} 
    Stack<Node> s = new Stack<Node>(); 
    Stack<Node> reverser = new Stack<Node>(); 
    s.push(r); 
    while(!s.isEmpty()){ 
     Node temp = s.pop(); 
     reverser.push(temp); 
     if (temp.left != null){ 
      s.push(temp.left);} 
     if(temp.right != null){ 
      s.push(temp.right);} 
    } 
    while(!reverser.empty()){ 
     System.out.print(reverser.peek()); 
     reverser.pop(); 
    } 
} 

(via http://articles.leetcode.com/binary-tree-post-order-traversal/)

où l'essentiel, une pile inverse juste l'autre. Je suis juste très curieux de savoir comment cela fonctionne. J'ai une hypothèse que Stack s accepte l'entrée pour que la sortie soit quelque chose comme P -> R -> L, et il passe juste cela sur Stack inverser qui crache L -> R .-> P puisque c'est Last In First Out . Cependant, juste en essayant de réfléchir aux processus de cet algorithme, j'ai du mal à comprendre comment et pourquoi Stack s prend son entrée comme il le fait. En espérant que je pourrais avoir un aperçu ici! Merci :)

Answer 1

Le code que vous avez fourni est simplement une version en boucle de la solution récursive correspondante:

public void postOrderTraverseRecursive(Node r){ 
    if(r == null){return;} 

    if (r.left != null){ 
     postOrderTraverseRecursive(r.left);} 
    if(r.right != null){ 
     postOrderTraverseRecursive(r.right);} 

    System.out.print(r); 
} 

Afin de transformer récursion à une boucle, nous devons reverse the order of the statements execution. Nous allons utiliser une pile pour gérer les invocations de récurrence, et une pour conserver la sortie de la récursivité (c'est-à-dire les arguments d'instruction System.out.print).

Votre code avec plus significatifs noms de variables et explication:

public void postOrderTraverse(Node root){ 
    if(root == null){return;} 
    Stack<Node> recursionStack = new Stack<Node>(); 
    Stack<Node> printStack = new Stack<Node>(); 
    recursionStack.push(root); 
    while(!recursionStack.isEmpty()){ 
     Node node = recursionStack.pop(); 
     /* Recursion iteration start */ 
     // According to the recursion we should process left->right->node. 
     // Considering that in the loop version we have to reverse the order of invocations, 
     // we are processing node->right->left 
     printStack.push(node); // node is added to printStack immediately 
     // left is added to recursionStack first, but because 
     // of the FILO nature of the stack it will be processed last 
     if (node.left != null){ 
      recursionStack.push(node.left);} 
     // right is added to recursionStack last, but because 
     // of the FILO nature of the stack it will be processed first 
     if(node.right != null){ 
      recursionStack.push(node.right);} 
     /* Recursion iteration end */ 
    } 
    // We've processed all the input and now we have reversed 
    // history of the prints, processing them in reverse order 
    // to receive the actual one 
    while(!printStack.empty()){ 
     System.out.print(printStack.peek()); 
     printStack.pop(); 
    } 
}