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

难度：中级 关键词：图搜索算法（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 ---来自腾讯云社区的---三猫