C++實(shí)現(xiàn)二叉樹(shù)層序遍歷的方法

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

二叉樹(shù)層序遍歷

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

層序遍歷二叉樹(shù)是典型的廣度優(yōu)先搜索 BFS 的應(yīng)用，但是這里稍微復(fù)雜一點(diǎn)的是，要把各個(gè)層的數(shù)分開(kāi)，存到一個(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è)一維向量存到二維向量里，以此類推，可以完成層序遍歷，參見(jiàn)代碼如下：

解法一：

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

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

解法二：

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)二叉樹(shù)層序遍歷的方法”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會(huì)為大家更新不同的知識(shí)，如果還想學(xué)習(xí)更多的知識(shí)，請(qǐng)關(guān)注億速云行業(yè)資訊頻道。