前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode刷题DAY 15:二叉树的层序遍历

LeetCode刷题DAY 15:二叉树的层序遍历

作者头像
三猫
发布2020-05-20 01:12:59
4050
发布2020-05-20 01:12:59
举报
文章被收录于专栏:机器学习养成记

难度:中级 关键词:图搜索算法(BFS、DFS)

1 题目描述

根据层序遍历返回一棵二叉树的节点值(逐层从左至右访问)。比如输入如下树:

返回[[3],[9,20],[15,7]]。

2 题解

BFS、DFS是两个图搜索算法,本题的关键也是这两个算法的理解与使用。

上图可帮助宏观理解两种搜索算法差异,下面我们来具体说明。

思路一:广度优先算法(BFS)

广度优先算法(Breadth-First-Search, BFS)指先访问当前节点的所有邻接节点,然后再不断扩张,是一种依靠队列实现的算法(先进先出,把每个还没有搜索到的点依次放入队列,然后再弹出队列的头部元素当做当前遍历点)。本题因为要逐层输出,所以要对每一层节点进行区分:

  • step 1:level为记录当层节点的序列,首先把根节点放入序列中。
  • step 2:通过循环,依次将level首部的节点取出,res记录节点的值,tmp1记录其左右节点。当循环结束时,将res加入最后结果序列result中,将level更新为tmp1的值。
  • step 3:重复step 2,直至level为空。
  • step 4:输出result。

以题目描述中的例子为例,计算过程如下:

代码语言:python
代码运行次数:0
复制
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:    
    def levelOrder(self, root: TreeNode) -> List[List[int]]:        
        if not root:            
            return []        
        result = []        
        level = [root]        
        while len(level)>0:            
            tmp1=[]            
            res = []            
            for node in level:                
                if node.left:                    
                    tmp1.append(node.left)                
                if node.right:                    
                    tmp1.append(node.right)                
                res.append(node.val)            
            level = tmp1            
            result.append(res)        
        return result

思路二:深度优先算法(DFS)

深度优先算法(Depth-First-Search, DFS)指先在一个方向上访问所有节点,该方向没有节点时回到上一层进行扩张,是一种依靠递归实现的算法。

  • step 1:result为记录最终结果的列表,首先访问根节点,并记录其层数。
  • step 2:判断result中是否有记录该层的列表,如没有则添加,如有则放到最后。
  • step 3:依次访问左、右节点,重复step 2,直至节点为空跳出。
  • step 4:输出result。

计算过程如下:

代码语言:python
代码运行次数:0
复制
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:    
    def levelOrder(self, root: TreeNode) -> List[List[int]]:        
        result = []        
            def rootLevel(root,level):            
                if not root:                
                    return            
                # result中无对应level的列表,进行添加            
                if len(result)<level+1:                
                    result.append([])            
                # 将该节点值存入该level列表最后            
                result[level].append(root.val)            
                # 因为从左到右输出,先访问左节点再右节点            
                rootLevel(root.left,level+1)            
                rootLevel(root.right,level+1)        
            rootLevel(root,0)        
            return result

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-05-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 机器学习养成记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1 题目描述
  • 2 题解
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档