二叉树前序遍历的两种迭代解的区别

Question

截至目前，我还试图通过在 Java 中使用 Stack 对象来获得对递归的直观理解。在 GeeksForGeeks 上，他们有关于二叉树遍历方法的练习题。目前我在 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 子节点压入栈顶，然后访问该子节点。因此，修改您的代码，如下所示-

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

   }
}

二叉树前序遍历的两种迭代解的区别

Difference Between Two Iterative Solutions for PreOrder Traversal of a Binary Tree

java

iteration

binary-tree

preorder