c++ - 二叉树上的左右 BFS 遍历

Question

这不是家庭作业。我在考虑树遍历中的一些新问题，这似乎很明显所以想解决它。

问题与 BFS 之类的层序遍历非常相似。在 BFS 中，我们通常在树的每一层从左到右移动，但在这里如果我们在第 i 层从左到右移动，那么第 (i-1) 和 (i+1) 层需要从右到左移动。

例如:

           2
          / \
         7   5
        / \   \
       2   6   9
          / \   \
         5  11   4

在正常的 BFS 中，我们输出:2, 7, 5, 2, 6, 9, 5, 11, 4

但我正在寻找一个输出的解决方案:2, 5, 7, 2, 6, 9, 4, 11, 5

我能够想出一个解决方案。但是，我想看看是否有人提出比我更好的解决方案。我也特别关注空间复杂度(堆栈大小)的优化。

请按照C++语言给出你的逻辑。如果您不在您的解决方案中使用任何容器或 STL，我将不胜感激。

---

根据此处的评论，我想出了一个使用两个堆栈的解决方案。我的解决方案如下。

• 创建堆栈 S1 和 S2 以及队列 Q。队列 Q 将保存最终答案。
• 请注意，在压入任何堆栈(S1 或 S2)之前，我们将首先将其排入队列 Q。
• 无论我们从堆栈 s1 弹出什么，我们都会将其(第一个)右 child 和(然后)左 child (按此顺序)插入堆栈 s2。 (记住第 2 点)
• 无论我们从堆栈 s2 弹出什么，我们都会将其(第一个)左 child 和(然后)右 child (按此顺序)插入堆栈 s1。 (记住第 2 点)
• 从一个堆栈中弹出并将其插入另一个堆栈，直到两个堆栈都为空。队列中的最终条目将是 ans。

---

/*
Create Stack S1, S2; // for tmp itr. Both of size log<n>
Create Queue Q; // It will hold ans
*/ 


Q.enqueue(root); //Enqueue the root nood;
S1.enqueue(root); //Fill the stack with somthing to start.



  while(S1||S2){                        // keep spinning untill both stack are empty.
        while(s1){                      //take care of stack S1.
            Node* tmp = S1.pop();       //take top elem;

        if(tmp->right){
            Q.enqueue(tmp->right);
            S2.push(tmp->right);
        }

        if(tmp->left){
            Q.enqueue(tmp->left);
            S2.push(tmp->left);
        }
    }

    while(S2){ //while S2 is not empty
        Node* tmp = S2.pop();

        if(tmp->left){
            Q.enqueue(tmp->left);
            S1.push(tmp->left);
        }

        if(tmp->right){
            Q.enqueue(tmp->right);
            S1.push(tmp->right);
        }

    }
} //End of outher while

while(Q){
    cout<< Q.pop()->data;   //output the entries in desired format.
}

---

我觉得还可以(如果不行请告诉我)。但仍然想知道是否有任何其他可能的解决方案(比这更好)。

Answer 1

与其使用单个队列，不如使用一对堆栈。当当前堆栈为空时，开始从另一个堆栈中弹出节点，并将它们的子节点推到现在为空的堆栈中。

所以你有

• 将 2 推到其中一叠。
• 从中弹出 2，将 7 5 推到另一个上。交换堆栈。
• 弹出 5，推 9。
• 弹出 7，推 6 2. 交换筹码。

等等

您还需要一个状态变量来决定是先向左推还是向右推。