Почему 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, так как это Last In First Out,

Однако, просто пытаясь продумать процессы этого алгоритма, я изо всех сил пытаюсь понять, как и почему Stack s получает свой вклад так, как он это делает. Надеюсь, я смогу кое-что понять здесь! Спасибо:)

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

Чтобы преобразовать рекурсию в цикл, нам нужно изменить порядок выполнения операторов. Мы будем использовать один стек для поддержки вызовов рекурсии и один для поддержки вывода рекурсии (т.е. 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();
    }
}