博客
关于我
[leetcode]102. Binary Tree Level Order Traversal
阅读量:540 次
发布时间:2019-03-09

本文共 1317 字,大约阅读时间需要 4 分钟。

要解决这个问题,我们需要对二叉树进行层序遍历。层序遍历是指从树的根节点开始,逐层从左到右访问所有节点,直到遍历完所有节点。常用方法是广度优先搜索(BFS),使用队列来辅助实现。

方法思路

  • 检查根节点:如果根节点为空,直接返回一个空的结果列表。
  • 初始化队列:将根节点加入队列。
  • 处理队列:在每次循环中,记录当前队列的大小(表示当前处理的层有多少个节点)。然后,遍历这个数量的节点,每个节点取出队列,记录其值,接着将其左孩子和右孩子加入队列(如果不为空)。
  • 记录层序:每次处理完一层节点后,将该层的节点值添加到结果列表中。
  • 解决代码

    import java.util.ArrayList;import java.util.List;import java.util.Queue;import java.util.LinkedList;public class Solution {    public List
    > levelOrder(TreeNode root) { List
    > result = new ArrayList<>(); Queue
    queue = new LinkedList<>(); if (root == null) { return result; } queue.offer(root); while (!queue.isEmpty()) { int num = queue.size(); List
    level = new ArrayList<>(); for (int i = 0; i < num; i++) { TreeNode current = queue.poll(); level.add(current.value); if (current.left != null) { queue.offer(current.left); } if (current.right != null) { queue.offer(current.right); } } result.add(level); } return result; }}

    代码解释

  • 初始化结果列表:使用 ArrayList 来存储每一层的节点值。
  • 队列初始化:使用 LinkedList 作为队列,用于广度优先遍历。
  • 根节点检查:如果根节点为空,直接返回空列表。
  • 队列填充:将根节点加入队列。
  • 处理循环:在每次循环中,记录当前队列的大小 num,表示当前层的节点数。
  • 处理每个节点:取出队列中的节点,记录其值。将其左孩子和右孩子(不为空时)加入队列。
  • 记录层序:将当前层的节点值添加到结果列表中。
  • 返回结果:当队列处理完毕后,返回结果列表。
  • 这种方法确保了每一层的节点按顺序被访问和记录,得到的结果符合层序遍历的要求。

    转载地址:http://wehiz.baihongyu.com/

    你可能感兴趣的文章
    Python与Excel的完美邂逅:深入浅出,手把手教你轻松玩转Excel数据操作
    查看>>
    python与flask_Python编程中flask的简介与简单使用
    查看>>
    python与图灵机器人交互(WXPY版本)
    查看>>
    python与运算符_python运算符
    查看>>
    python两个列表获取交集,并集,差集
    查看>>
    python两个字典合并,两个list合并
    查看>>
    Python两个版本共存时,命令行升级pip
    查看>>
    Python两个版本共存时,怎么验证是否安装成功 scrapy
    查看>>
    Python两个版本共存时,通过pip安装Scrapy
    查看>>
    python两组变量的相关关系散点图_变量是什么?变量间的两种关系——函数关系和相关关系(小学版)...
    查看>>
    Python中 pass语句的作用
    查看>>
    python中 urllib, urllib2, httplib, httplib2 几个库的区别
    查看>>
    python中 yaml库 & json库 & xmltodict库使用
    查看>>
    python中 将你的名字转化成为二进制并输出
    查看>>
    Python中*args 和**kwargs的用法
    查看>>
    Python中*args 和**kwargs的用法
    查看>>
    python中0、1、True、False、if条件
    查看>>
    python中argparse模块关于 parse_args() 函数详解(全)
    查看>>
    python中base64编码与解码
    查看>>
    python中break怎么用_详解Python中break语句的用法
    查看>>