目錄
定義
層序遍歷的數據結構
實現過程簡述
具體代碼
定義
層序遍歷就是從左到右一層一層地遍歷二叉樹。
層序遍歷的數據結構
層序遍歷需要借用一個輔助數據結構實現，由于隊列具有先進先出的特性，符合一層一層遍歷的邏輯，而棧先進后出更適合模擬深度優先遍歷（遞歸）。
實現過程簡述
首先如果根節點不為空，就將根節點放入隊列里。然后設置循環，循環結束條件為隊列為空（這樣就可以保證遍歷完二叉樹中的每一個節點）。循環體里記錄每層的節點數量，并設置一個節點指針保存隊列首元素（以便后續使用），將首元素的值放入一個一維數組中，然后彈出首元素。使用節點指針將該節點的左子節點和右子節點放入隊列。一層結束將一維數組push進結果數組（二維數組）里。遍歷完畢返回結果數組。
具體代碼
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;vector<vector<int>> result;if(root != nullptr) que.push(root);while(!que.empty()) {int size = que.size();vector<int> vec;while(size--) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if(node->left) que.push(node->left);if(node->right) que.push(node->right);}result.push_back(vec);} return result;}
};
