LeetCode-102 二叉树的层序遍历 粒子

📝题目

给定一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有节点)。

示例:

二叉树:[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
   
返回其层次遍历结果:

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


📝思路

想法一:递归遍历。难点大概就是如何加入新的一层。
想法二:BFS(广度优先搜索)。利用队列先进先出的特性逐层存储、读取和弹出子节点。
🐣:都是上学期数据结构的内容,有点遗忘了…

📝题解

//想法一

void traverse(vector<vector<int>>& result, int depth, TreeNode* root){
    if (root == NULL)   return;
    if (depth >= result.size())
        result.push_back(vector<int> {});
    result[depth].push_back(root->val);
    traverse(result, depth+1, root->left);
    traverse(result, depth+1, root->right);
}
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    traverse(result, 0, root);
    return result;
}
//想法二

vector<vector<int>> levelOrder(TreeNode* root){
    queue<TreeNode*> q;
    vector<vector<int>> result;
    if (root != NULL)
        q.push(root);
    
    while(!q.empty()){
        int count = q.size();
        vector<int> layer;
        while(count > 0){
            TreeNode* tmp = q.front();
            q.pop();
            layer.push_back(tmp->val);
            if (tmp->left != NULL)  q.push(tmp->left);
            if (tmp->right != NULL)  q.push(tmp->right);
            count --;
        }
        result.push_back(layer);
    }
    return result;
}