今天小編給大家分享一下C++實現二叉樹層序遍歷的方法的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

創新互聯專注于峽江網站建設服務及定制，我們擁有豐富的企業做網站經驗。 熱誠為您提供峽江營銷型網站建設，峽江網站制作、峽江網頁設計、峽江網站官網定制、重慶小程序開發公司服務，打造峽江網絡公司原創品牌,更為您提供峽江網站排名全網營銷落地服務。

二叉樹層序遍歷

Given a binary tree, return the level order traversal of its nodes" values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
/
9  20
/ 
15   7

return its level order traversal as:

[
[3],
[9,20],
[15,7]
]

層序遍歷二叉樹是典型的廣度優先搜索 BFS 的應用，但是這里稍微復雜一點的是，要把各個層的數分開，存到一個二維向量里面，大體思路還是基本相同的，建立一個 queue，然后先把根節點放進去，這時候找根節點的左右兩個子節點，這時候去掉根節點，此時 queue 里的元素就是下一層的所有節點，用一個 for 循環遍歷它們，然后存到一個一維向量里，遍歷完之后再把這個一維向量存到二維向量里，以此類推，可以完成層序遍歷，參見代碼如下：

解法一：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> res;
        queue<TreeNode*> q{{root}};
        while (!q.empty()) {
            vector<int> oneLevel;
            for (int i = q.size(); i > 0; --i) {
                TreeNode *t = q.front(); q.pop();
                oneLevel.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            res.push_back(oneLevel);
        }
        return res;
    }
};

下面來看遞歸的寫法，核心就在于需要一個二維數組，和一個變量 level，關于 level 的作用可以參見博主的另一篇博客 Binary Tree Level Order Traversal II 中的講解，參見代碼如下：

解法二：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        levelorder(root, 0, res);
        return res;
    }
    void levelorder(TreeNode* node, int level, vector<vector<int>>& res) {
        if (!node) return;
        if (res.size() == level) res.push_back({});
        res[level].push_back(node->val);
        if (node->left) levelorder(node->left, level + 1, res);
        if (node->right) levelorder(node->right, level + 1, res);
    }
};

以上就是“C++實現二叉樹層序遍歷的方法”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注創新互聯行業資訊頻道。

網頁標題：C++實現二叉樹層序遍歷的方法
本文路徑：http://www.yijiale78.com/article36/jjpesg.html

成都網站建設公司_創新互聯，為您提供網站內鏈、微信公眾號、域名注冊、微信小程序、定制開發、網站建設

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯