這次來寫一下 LeetCode 的第 102 題，二叉樹的層次遍歷。

題目描述

題目直接從 LeetCode 上截圖過來，題目如下：

102.二叉樹的層次遍歷題目

上面的題就是 二叉樹的層次遍歷 題目的截圖，同時 LeetCode 會根據選擇的語言給出一個類的定義或者函數的定義，然后在其中實現 二叉樹的層次遍歷 的解題過程。這次我使用 C++ 語言來進行完成。

C++ 語言給出的函數定義如下：

/** * 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> levelOrder(TreeNode* root) { }};

通過函數定義可以看出，levelOrder 函數的參數是一個二叉樹的根節點，然后返回的值是一個二維數組，我們要做的就是按照層次來遍歷這個二叉樹，并且將二叉樹每層的值需要保存在二維數組中并返回。

問題分析

該題目是一個比較好理解的題目，因為題目中已經明確了需要使用層次遍歷二叉樹來得到每個節點上的值，且不同層次上節點的數據保存在不同的數組中，最后每個層次的數組構成一個二維數組。

拿題目中給出的例子來說明什么是層次遍歷，如下圖。

二叉樹的層次

在圖中，3 是第一層，9 和 20 是第二層，15 和 7 是第三層，通過遍歷這個二叉樹按層次來分別把它們保存到不同的數組中，最后構成一個二維數組返回。

二叉樹的層次遍歷需要使用另外一個數據結構來協助進行遍歷，另外的那個數據結構就是“隊列”。隊列的作用是保留每一層的從左到右的順序，進而使得我們在進行層次遍歷的時候，可以按照從左往右的順序完成層次遍歷。

首先在遍歷之前，使根節點先進入隊列，隊列中有了根節點后，就可以進入循環。進入循環后，首先獲取隊頭的元素，并讓隊頭元素出隊，目前也就是根節點，通過出隊的元素分別得到它的左孩子和右孩子，并讓它的左孩子和右孩子進入臨時隊列(有可能左孩子和右孩子不同時存在，反正存在哪個哪個進入隊列即可)。然后保存當前節點的元素到數組中。然后臨時隊列中的元素，進入真正要進行循環獲取層次的隊列，隊列中始終要保持只有當前層次的節點。

由于篇幅有限，可能無法很好的把其方式描述清楚，但是看代碼會很直觀。

代碼實現

C++ 的代碼如下：

/** * 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> levelOrder(TreeNode* root) { vector> vec; if (root == NULL) { return vec; } // 隊列保存樹的根節點 queue que; que.push(root); while (!que.empty()) { // 保存當前層上節點的值 vector v; // 臨時隊列 queue tmp; while (!que.empty()) { TreeNode *p = que.front(); que.pop(); // 左右節點入隊 if (p->left) { tmp.push(p->left); } if (p->right) { tmp.push(p->right); } v.push_back(p->val); } // 下一層的節點入隊 while (!tmp.empty()) { que.push(tmp.front()); tmp.pop(); } vec.push_back(v); } return vec; }};

從代碼中可以看出，整個代碼是一個兩層 while 循環，外層的 while 循環用來遍歷整棵二叉樹，內層 while 循環是用來遍歷二叉樹相同層的每個節點。代碼中，我引入了兩個隊列，分別是 que 和 tmp，que 隊列是用來進行遍歷當前層的每個節點的，tmp 隊列是用來臨時保存當前層的左孩子和右孩子節點的。

提交結果

在寫完代碼后，點擊右下角的 “執行代碼”，然后觀察 “輸出” 和 “預期結果” 是否一致，一致的話就點擊 “提交” 按鈕。點擊 “提交” 按鈕后，系統會使用更多的測試用例來測試我們寫的函數體，如果所有的測試用例都通過了，那么就會給出 “通過” 的字樣，如果沒有通過，會給出失敗的那一組測試用例，我們可以根據給出的測試用例來繼續修改代碼。我們的代碼提交后的截圖如下：

執行結果

類似這樣需要引入其他數據結構輔助完成的題目，我個人覺得使用 C 語言就比較難，就拿這道題目來說，層次遍歷二叉樹本身就是兩層的 while 循環了，還要引入隊列去輔助完成，像 C 語言這樣沒有現成的集合可以使用，我還要自己去完成一個隊列的數據結構去進行管理么？不知道有什么好的方法。

總結

以上是生活随笔為你收集整理的c++根据二叉树的层次遍历建立二叉树_LeetCode | 102.二叉树的层次遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。