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

創(chuàng)新互聯(lián)專注于峽江網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠為您提供峽江營銷型網(wǎng)站建設(shè)，峽江網(wǎng)站制作、峽江網(wǎng)頁設(shè)計(jì)、峽江網(wǎng)站官網(wǎng)定制、重慶小程序開發(fā)公司服務(wù)，打造峽江網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供峽江網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。

二叉樹層序遍歷

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]
]

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

解法一：

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        if (!root) return {};
        vector> res;
        queue q{{root}};
        while (!q.empty()) {
            vector 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;
    }
};

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

解法二：

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        vector> res;
        levelorder(root, 0, res);
        return res;
    }
    void levelorder(TreeNode* node, int level, vector>& 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++實(shí)現(xiàn)二叉樹層序遍歷的方法”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學(xué)習(xí)更多的知識，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。