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

三猫

发布于 2020-05-20 01:12:59

4060

发布于 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。

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

# 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。

计算过程如下：

# 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 条评论

热度