Разница между двумя итерационными решениями для обхода предварительного заказа двоичного дерева

Question

На данный момент я пытаюсь получить интуитивное понимание рекурсии, также работая над использованием объекта Stack в Java.На GeeksForGeeks у них есть практические проблемы с методами обхода в двоичном дереве.В настоящее время я нахожусь на PreOrder и, хотя я разобрался с рекурсивным решением, итеративное решение оказывается довольно проблематичным.Когда я нашел реальный ответ на проблему, я обнаружил, что мой код практически идентичен коду решения.Некоторое время я ходил взад и вперед, пытаясь понять, почему мое итеративное решение для обхода PreOrder неверно по сравнению с реальным решением, но подумал, что, возможно, мне нужен третий набор более опытных глаз, чтобы сказать мне, почему янеправильно.

Вот URL-адрес проблемы и онлайн-компилятор: https://practice.geeksforgeeks.org/problems/preorder-traversal/1

Вот мой код:

void preorder(Node root)
{
   // Your code goes here
   if(root == null) return;
   Stack<Node> stack = new Stack<Node>();

   stack.push(root);
   while(!stack.isEmpty()) {
       Node cur = stack.pop();
       System.out.print(cur.data + " ");

       if(cur.left != null) {
           stack.push(cur.left);
       }
       if(cur.right != null) {
           stack.push(cur.right);
       }
   }
}

Вот код решения:

void preorder(Node root) { 

    // Base Case 
    if (root == null) { 
        return; 
    } 

    // Create an empty stack and push root to it 
    Stack<Node> nodeStack = new Stack<Node>(); 
    nodeStack.push(root); 

    /* Pop all items one by one. Do following for every popped item 
     a) print it 
     b) push its right child 
     c) push its left child 
     Note that right child is pushed first so that left is processed first 
*/
    while (nodeStack.empty() == false) { 

        // Pop the top item from stack and print it 
        Node mynode = nodeStack.peek(); 
        System.out.print(mynode.data + " "); 
        nodeStack.pop(); 

        // Push right and left children of the popped node to stack 
        if (mynode.right != null) { 
            nodeStack.push(mynode.right); 
        } 
        if (mynode.left != null) { 
            nodeStack.push(mynode.left); 
        } 
    } 
} 

Answer 1

Обратный порядок для бинарного дерева: Visit,Left and Right.

Ваш код не похож на код решения.

Вам нужно сначала поместить right дочерний элемент в стек, а затем left дочерний элемент, чтобы вывести left дочерний элемент поверх стека, а затем посетить этого дочернего элемента.Следовательно, измените ваш код, как показано ниже -

void preorder(Node root)
{
   // Your code goes here
   if(root == null) return;
   Stack<Node> stack = new Stack<Node>();

   stack.push(root);
   while(!stack.isEmpty()) {
       Node cur = stack.pop();
       System.out.print(cur.data + " ");

       if(cur.right != null) {
           stack.push(cur.right);
       }

       if(cur.left != null) {
           stack.push(cur.left);
       }

   }
}