LeetCode 题目 102:二叉树的层序遍历

简介: LeetCode 题目 102:二叉树的层序遍历

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

python源码解读

程序员必备的数学知识与应用

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

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

示例

示例

输入:

3
   / \
  9  20
    /  \
   15   7

输出:

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

方法一:迭代使用队列

解题步骤
  1. 初始化:使用一个队列来存储每一层的节点。
  2. 迭代处理:每次迭代开始时,记录当前队列的长度,这代表了当前层的节点数;然后从队列中逐个取出节点,将其值加入当前层的结果列表,并将其子节点加入队列以用于下一次迭代。
Python 示例
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def levelOrder(root):
    """
    使用队列实现二叉树的层序遍历
    :param root: TreeNode, 二叉树的根节点
    :return: List[List[int]], 层序遍历的结果
    """
    if not root:
        return []
    result, queue = [], [root]
    while queue:
        level_size = len(queue)
        current_level = []
        for _ in range(level_size):
            node = queue.pop(0)
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(current_level)
    return result
算法分析
  • 时间复杂度:(O(n)),每个节点被访问一次。
  • 空间复杂度:(O(n)),队列中最多同时存储两层节点。
算法改进

尽管迭代使用队列的方法对于层序遍历非常直观和高效,但它也有一些潜在的问题和限制。

1. 空间复杂度
  • 问题:在最坏的情况下(例如完全二叉树),队列可能需要存储树中所有的叶子节点,这大约是节点总数的一半,因此空间复杂度可以达到 (O(n))。
  • 改进:虽然对于层序遍历来说,这种空间需求通常是不可避免的,但可以通过优化数据结构的选择或者在特定情况下采用不同的遍历策略来减轻空间压力。
2. 效率问题
  • 问题:在 Python 中,使用列表作为队列并进行频繁的 pop(0) 操作是低效的,因为这是一个 (O(n)) 的操作。
  • 改进:可以使用 collections.deque,它支持 (O(1)) 时间复杂度的 append 和 popleft 操作,这样可以显著提高效率。
3. 并发处理
  • 问题:当前的队列方法是单线程的,对于非常大的树,这可能导致性能瓶颈。
  • 改进:可以考虑使用并行或并发技术来处理不同的树层。例如,可以在多线程环境中为每一层的遍历分配一个线程,但这需要处理线程同步的问题,确保层序的顺序性。

Python 示例代码改进

以下是考虑了上述改进后的 Python 示例代码:

from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def levelOrder(root):
    """
    使用 deque 实现二叉树的层序遍历
    :param root: TreeNode, 二叉树的根节点
    :return: List[List[int]], 层序遍历的结果
    """
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        current_level = []
        for _ in range(level_size):
            node = queue.popleft()  # 使用 deque 提高出队效率
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(current_level)
    return result

在这个改进版本中,我使用了 collections.deque 来优化队列操作,这样 popleft()append() 都是 (O(1)) 的操作,有效提高了遍历的效率。

通过这些改进,可以解决一些原始方法中存在的效率和性能问题,使得层序遍历更加高效和适应更多复杂的应用场景。

方法二:递归

解题步骤
  1. 定义递归函数:使用一个辅助函数来处理每一层的节点。函数接收当前的节点和节点的层级作为参数。
  2. 递归逻辑:将节点的值添加到其对应层级的列表中。递归地处理左子节点和右子节点,层级参数加一。
Python 示例
def levelOrder(root):
    """
    递归实现二叉树的层序遍历
    :param root: TreeNode
    :return: List[List[int]]
    """
    def helper(node, level):
        if not node:
            return
        if len(result) == level:
            result.append([])
        result[level].append(node.val)
        helper(node.left, level + 1)
        helper(node.right, level + 1)
    result = []
    helper(root, 0)
    return result
算法分析
  • 时间复杂度:(O(n)),每个节点访问一次。
  • 空间复杂度:(O(h)),递归栈的深度,其中 (h) 是树的高度。

不同算法的优劣势对比

特征 方法一:迭代队列 方法二:递归
时间复杂度 (O(n)) (O(n))
空间复杂度 (O(n)) (O(h))
优势 直接且实用 简洁明了
劣势 空间开销大 依赖栈深度

应用示例

层序遍历在许多场景中都非常有用,比如在图形界面中显示树结构、在网络服务中以层序格式发送数据结构、以及在 AI 和机器学习中构建决策树时评估节点。


欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
11天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
11 3
|
21天前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
11 1
|
6天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
算法
二刷力扣--二叉树(3)
二刷力扣--二叉树(3)
|
1月前
二刷力扣--二叉树(2)
二刷力扣--二叉树(2)
|
1月前
二刷力扣--二叉树(1)基础、遍历
二刷力扣--二叉树(1)基础、遍历
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
1月前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(4)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
1月前
|
存储 算法
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(1)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总