資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學每兩層改變方向的層序遍歷（C/C++ 實現）
層序遍歷
這是一種透過深度優先遍歷處理或列印二叉樹所有節點的演算法，從根節點開始，依次遍歷其子節點，以此類推。
示例
輸入 −
輸出 −
2 4 7 3 6 11
此任務涉及列印二叉樹的層序遍歷，前兩層從右到左列印，接下來的兩層從左到右列印，依次類推。挑戰在於二叉樹的層序遍歷必須每兩層反轉一次。
請參考示例輸入以更好地理解問題。
輸入 −
輸出 −
2 3 7 11 12 6 5 19 23 16 13 9 21 17 18 1 20
在上圖中，第 1 層和第 2 層從左到右列印，然後是第 3 層和第 4 層，它們從右到左列印，第 5 層從左到右列印。
方法
我們將使用佇列和棧來解決這個問題。每兩層之後，使用棧來改變遍歷方向，佇列用於正常的層序遍歷。
使用標準的層序遍歷方法列印二叉樹的前兩層。
我們將宣告兩個變數：`count=0` 用於儲存我們正在遍歷的層級，以及一個名為 `rightToLeft=false` 的布林變數，用於從右到左列印元素。
每當 `count=2` 時，我們將 `!rightToLeft` (非運算) 儲存到 `rightToLeft` 中，並將 `count` 設定為 0。
當 `rightToLeft=true` 時，我們將節點壓入棧中，而不是列印它們。一旦當前層的節點都壓入棧中，我們就列印棧中的節點。
因為棧遵循後進先出 (LIFO) 的原則，所以我們可以使用棧來反向列印節點。
接下來的兩層，我們將使用層序遍歷方法從左到右列印節點，然後再次使用棧從右到左列印接下來的兩層節點，以此類推。
透過結合使用佇列和棧，我們可以實現每兩層改變方向的層序遍歷。
示例
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int data;
TreeNode*left;
TreeNode*right;
TreeNode (int d){
data=d;
left=NULL;
right=NULL;
}
};
void printEveryTwoLevelOrderTraversal(TreeNode* root){
//when the node is null
if(root==NULL){
return;
}
// when root left and right is null
if(root->left==NULL && root->right==NULL){
cout<<root->data<<endl;
return;
}
queue<TreeNode*> Queue; // queue is for traversing the level
stack<TreeNode*> Stack; // stack is for printing the node in reverse order once popped out from the queue
int count=0;
bool direction = false;
Queue.push(root); // root node is pushed inside the queue
while(!Queue.empty()){
int size=Queue.size();
count++;
for(int i=0;i<size;i++){
TreeNode* tmp=Queue.front();
Queue.pop();
if(direction==false){ // print the node from left to right once the node is popped out from the queue
cout<<tmp->data<<" ";
}
else{ // it stores the node in the stack for printing right to left
Stack.push(tmp);
}
if(tmp->left!=NULL){
Queue.push(tmp->left);
}
if(tmp->right!=NULL){
Queue.push(tmp->right);
}
}
if(direction==true){
while(!Stack.empty()){
TreeNode* tmp=Stack.top();
Stack.pop();
cout<<tmp->data<<" ";
}
}
if(count==2){ // change the direction after every two level
direction=!direction;
count=0;
}
cout<<endl;
}
}
int main(){
TreeNode* node=new TreeNode(5);
node->left=new TreeNode(7);
node->right=new TreeNode(8);
node->left->left=new TreeNode(4);
node->left->right=new TreeNode(9);
node->left->left->left=new TreeNode(10);
node->left->left->right=new TreeNode(14);
node->right->left=new TreeNode(11);
node->right->right=new TreeNode(12);
printEveryTwoLevelOrderTraversal(node);
return 0;
}
輸出
5 7 8 12 11 9 4 14 10
時間複雜度：O(n)。 時間複雜度為 O(n)，因為每個節點在遍歷過程中最多隻遍歷兩次。
空間複雜度：O(n)，因為二叉樹中節點的數量將是棧或佇列的大小。
在本文中，我們嘗試解釋如何列印每兩層改變方向的層序遍歷。我希望這篇文章能幫助你理解這個概念。
123 次瀏覽
