1.層序遍歷
層序遍歷是從上到下從左到右每一層地去遍歷，
這與佇列的操作相似，先進先出
因此我們可以用佇列來實作：首先將根節點入隊，再出隊與此同時將根節點的左右兒子入隊，以此類推，直到佇列為空，（與BFS相似）
<iframe id="QMwGIS6Z-1613733046607" src="https://player.bilibili.com/player.html?aid=416806366" allowfullscreen="true" data-mediaembed="bilibili"></iframe>
二叉樹之層序遍歷
力扣習題：
102. 二叉樹的層序遍歷
給你一個二叉樹，請你回傳其按 層序遍歷 得到的節點值， （即逐層地，從左到右訪問所有節點），
示例：
二叉樹：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
回傳其層序遍歷結果：
[
[3],
[9,20],
[15,7]
]
代碼決議：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root)
{
queue<TreeNode*>q;
if(root!=NULL)q.push(root);//如果根節點不為空，則優先進佇列
vector<vector<int>> result;//創建一個二維陣列，用于存放每一層的一位陣列
while(!q.empty())
{//下面的size即當前這一層的大小
int size=q.size();//注意，這里的size要設定成當前佇列的大小，因為q.size（）會變動，而我們只要初始狀態的大小
vector<int>vec;//創建一個存放當前層的數字的一維陣列
for(int i=0;i<size;i++)
{
TreeNode*node=q.front();//拿出頭元素
q.pop();//出佇列
vec.push_back(node->val);//將這個頭元素的左右兒子入佇列（如果存在的話）
if(node->left) q.push(node->left);
if(node->right)q.push(node->right);
}
result.push_back(vec);//將這一層數字存放在二維陣列
}
return result;
}
};```
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261320.html
標籤：AI