给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
image.png
BFS利用的结构是queue（先进先出）
方法1--迭代
运用数据结构中队列的知识，开始时队列helper中只有根节点；
访问helper中的每一个节点，依次将结点的值保存在列表tmp1中， 并将节点的左右孩子（如果有的话）加入临时列表tmp2
用临时列表tmp2替换helper，继续遍历，直到helper为空
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
helper = [root]
res = []
while helper:
tmp1 = []
tmp2 = []
for node in helper:
tmp1.append(node.val)
if node.left:
tmp2.append(node.left)
if node.right:
tmp2.append(node.right)
res.append(tmp1)
helper = tmp2
return res
方法2--递归
# 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]]:
res = []
def helper(root, depth):
if not root: return
if len(res) == depth:
res.append([])
res[depth].append(root.val)
helper(root.left, depth + 1)
helper(root.right, depth + 1)
helper(root, 0)
return res
方法3--求二叉树深度+带层次索引的前序遍历
明确问题：层次遍历二叉树，已数组形势打印输出
解题思路：
可不是简单的层次遍历，一维输出
需要体现深度，层次
先求出二叉树高度
再前序遍历，带上层次的索引
# 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]]:
depth = self.get_depth(root)
res = [[] for i in range(depth)]
self.fill(res,root,0)
return res
def fill(self,res,root,depth_index):
if not root:return
res[depth_index].append(root.val)
self.fill(res,root.left,depth_index+1)
self.fill(res,root.right,depth_index+1)
def get_depth(self,root):
if not root:return 0
return max(self.get_depth(root.left)+1,self.get_depth(root.right)+1)
网友评论