爲什麼2堆棧對於後序橫向如此有效

Question

所以我熟悉後序遍歷：

L - > R - > P（從左到右到父）。

我看到了可以執行相當漂亮使用2個疊一個序遍歷代碼：

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

（通過http://articles.leetcode.com/binary-tree-post-order-traversal/）

，其中從本質上講，一個堆棧只是反轉等。我只是很好奇這是如何工作的。我有一個假設，Stack s接受輸入，以便輸出將類似於P - > R - > L，並且它只是將它傳遞到堆棧反轉器，它將L - > R .-> P排出，因爲它是後進先出。

但是，只是想通過這個算法的過程來思考，我很努力地理解Stack如何以及爲什麼以它的輸入方式來處理它。希望我能在這裏得到一些見解！謝謝:)

Answer 1

您提供的代碼只是相應的遞歸解決方案的環路版本：

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

爲了改造遞歸循環，我們需要reverse the order of the statements execution。我們將使用一個堆棧來維護遞歸調用，一個維護遞歸的輸出（即System.out.print語句參數）。

你有更有意義的變量名和解釋代碼：

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