代码随想录阅读笔记-二叉树【层序遍历】

题目

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

102.二叉树的层序遍历

思路 

前面几篇博客中我们介绍了二叉树的递归遍历,迭代遍历以及统一迭代遍历,这三种遍历方式都属于二叉树的深度优先遍历,​​​​​​接下来我们再来介绍二叉树的另一种遍历方式:层序遍历。

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。

需要借用一个辅助数据结构即队列来实现,队列先进先出,符合一层一层遍历的逻辑,而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历,只不过我们应用在二叉树上。

使用队列实现二叉树广度优先遍历,动画如下:

102二叉树的层序遍历

这样就实现了层序从左到右遍历二叉树。

c++代码如下:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size,不要使用que.size(),因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};
# 递归法
class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth)
    {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

 时间复杂度:O(N)

 空间复杂度:O(N)

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-03-31 22:38:02       98 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-03-31 22:38:02       106 阅读
  3. 在Django里面运行非项目文件

    2024-03-31 22:38:02       87 阅读
  4. Python语言-面向对象

    2024-03-31 22:38:02       96 阅读

热门阅读

  1. C语言学习笔记二

    2024-03-31 22:38:02       41 阅读
  2. springMVC是什么?

    2024-03-31 22:38:02       40 阅读
  3. leetcode217-Intersection of Two Arrays

    2024-03-31 22:38:02       40 阅读
  4. JDK 21 中对虚拟线程的 DDR 支持

    2024-03-31 22:38:02       33 阅读
  5. 5.94 BCC工具之cachetop.py解读

    2024-03-31 22:38:02       43 阅读
  6. 怎么使用Redis模拟Session

    2024-03-31 22:38:02       39 阅读
  7. DDPM pytorch代码详细注释

    2024-03-31 22:38:02       32 阅读
  8. 学习笔记之嵌入式八股文(C语言)

    2024-03-31 22:38:02       31 阅读
  9. 2024.2.3力扣每日一题——石子游戏7

    2024-03-31 22:38:02       34 阅读
  10. 6 字符串、元组和字典

    2024-03-31 22:38:02       40 阅读