给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal
题解来源:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/tao-mo-ban-bfs-he-dfs-du-ke-yi-jie-jue-by-fuxuemin/
广度优先搜索(BFS)
模板
while queue 不空:
cur = queue.pop()
for 节点 in cur的所有相邻节点:
if 该节点有效且未访问过:
queue.push(该节点)
解答
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
queue = collections.deque()
queue.append(root)
res = []
while queue:
size = len(queue)
level = []
for _ in range(size):
cur = queue.popleft()
if not cur:
continue
level.append(cur.val)
queue.append(cur.left)
queue.append(cur.right)
if level:
res.append(level)
return res
深度优先搜索(DFS)
由于题目要求每一层的节点都是从左到右遍历,因此递归时也要先递归左子树、再递归右子树。
DFS 做本题的主要问题是: DFS 不是按照层次遍历的。为了让递归的过程中同一层的节点放到同一个列表中,在递归时要记录每个节点的深度 level。递归到新节点要把该节点放入 level 对应列表的末尾。
当遍历到一个新的深度 level,而最终结果 res 中还没有创建 level 对应的列表时,应该在 res 中新建一个列表用来保存该 level 的所有节点。
解答
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []
self.level(root, 0, res)
return res
def level(self, root, level, res):
if not root: return
if len(res) == level: res.append([])
res[level].append(root.val)
if root.left: self.level(root.left, level + 1, res)
if root.right: self.level(root.right, level + 1, res)