最近连续做了一些二叉树的遍历题,现在总结下规律
题目
在leetcode中
- 层次遍历1:给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。
- 层次遍历2:给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
- 路径和1:给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
- 路径和2:给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
解析
其实这四道题,本质都是一个,就是遍历二叉树节点,只是3,4题在遍历的时候会需要记录值,所以只要做完第一题,其他题在这个基础上改一改即可!
层次遍历
例如:
给定二叉树: [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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题框架
如图
代码
按照解题步骤,如下代码
判空
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
定义数据结构
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
nodes=[root]
res=[]
分析遍历的循环和跳出条件 非常重要!!
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
nodes=[root]
res=[]
while nodes: # 从上到下遍历
val=[] # 记录遍历过的值
for i in range(len(nodes)): #从左到右遍历一层
res.append(val) # 将记录完的值放入res中
return res
完成循环,返回结果
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
nodes=[root]
res=[]
while nodes:
val=[]
for i in range(len(nodes)):
node=nodes.pop(0)
val.append(node.val)
if node.left:
nodes.append(node.left)
if node.right:
nodes.append(node.right)
res.append(val)
return res
拓展题目
2. 层次遍历2
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
只需要将遍历的结果res倒序输出即可
return res[::-1]
3. 路径和1
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
示例:
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路稍稍修改如下
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
nodes=[(root,sum-root.val),]
res=[]
while nodes:
node,cur_sum=nodes.pop(0)
if not node.left and not node.right and cur_sum==0:
return True
if node.left:
nodes.append((node.left,cur_sum-node.left.val))
if node.right:
nodes.append((node.right,cur_sum-node.right.val))
return False
4. 路径和2
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
只需要
nodes=[(root,[root.val])]
其中[root.val],表示当节点到达root时,路径为[root.val],其他节点亦如此
同时,由于我们不再记录sum,(要记录也可以),所以我们最后直接比较路径和与sum的值相等作为正确条件
代码如下
def pathSum(self, root: TreeNode, sum_: int) -> List[List[int]]:
res=[]
if not root:
return res
nodes=[(root,[root.val]),]
while nodes:
node,tmp=nodes.pop(0)
if not node.left and not node.right and sum(tmp)==sum_:
res.append(tmp)
if node.left:
nodes.append((node.left,tmp+[node.left.val]))
if node.right:
nodes.append((node.right,tmp+[node.right.val]))
return res
总结
其实,几乎所有关于二叉树遍历的题都可以通过这种方式解决,比如z字形层次遍历,最小深度等等,你学会了吗?