今天小編給大家分享一下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)的是，要把各個(gè)層的數(shù)分開，存到一個(gè)二維向量里面，大體思路還是基本相同的，建立一個(gè) queue，然后先把根節(jié)點(diǎn)放進(jìn)去，這時(shí)候找根節(jié)點(diǎn)的左右兩個(gè)子節(jié)點(diǎn)，這時(shí)候去掉根節(jié)點(diǎn)，此時(shí) queue 里的元素就是下一層的所有節(jié)點(diǎn)，用一個(gè) for 循環(huán)遍歷它們，然后存到一個(gè)一維向量里，遍歷完之后再把這個(gè)一維向量存到二維向量里，以此類推，可以完成層序遍歷，參見代碼如下：

解法一：

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;
    }
};

下面來看遞歸的寫法，核心就在于需要一個(gè)二維數(shù)組，和一個(gè)變量 level，關(guān)于 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++實(shí)現(xiàn)二叉樹層序遍歷的方法”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學(xué)習(xí)更多的知識，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

網(wǎng)頁標(biāo)題：C++實(shí)現(xiàn)二叉樹層序遍歷的方法
本文路徑：http://jinyejixie.com/article36/jjpesg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站內(nèi)鏈、微信公眾號、域名注冊、微信小程序、定制開發(fā)、網(wǎng)站建設(shè)

廣告

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