python coding with ChatGPT 打卡第17天| 二叉树：找树左下角的值、路径总和

相关推荐
python coding with ChatGPT 打卡第12天| 二叉树：理论基础
python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历
python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历
python coding with ChatGPT 打卡第15天| 二叉树：翻转二叉树、对称二叉树
python coding with ChatGPT 打卡第16天| 二叉树：完全二叉树、平衡二叉树、二叉树的所有路径、左叶子之和

找树左下角的值

Key Points

找出树的最后一行的最左边的值

相关题目

513. 找树左下角的值

视频讲解

递归中带着回溯

重点分析

方法一：层序遍历

def findBottomLeftValue(root):queue_record = [root]res = root.valwhile queue_record:level_size = len(queue_record)for i in range(level_size):node = queue_record.pop(0)if i==0:res = node.valif node.left:queue_record.append(node.left)if node.right:queue_record.append(node.right)return res

方法二：层序遍历简洁版

class Solution(object):def findBottomLeftValue(self, root):if not root:return Nonequeue = [root]while queue:current = queue.pop(0)# 先右后左加入队列，确保左边的节点最后被处理，从而保留在current中if current.right:queue.append(current.right)if current.left:queue.append(current.left)# 循环结束时，current中存储的是最后一层最左边的节点return current.val

这段代码使用了BFS来确保按层遍历树的节点，并且通过在每层遍历时记录遍历到的第一个节点值，最终找到了最后一行最左边的值。请注意，这里故意先将右子节点加入队列，然后加入左子节点，是为了在处理每一层的节点时，最后处理左子节点，但是对于寻找最后一行最左边的值的目的而言，只需要记录每一层第一次访问的节点即可，因此实际上你可以按照正常的顺序（先左后右）加入队列，然后最后处理的节点即为所求。这样的处理方式更直观且易于理解。

方法三：递归法

class Solution:def findBottomLeftValue(self, root: TreeNode) -> int:self.max_depth = float('-inf')self.result = Noneself.traversal(root, 0)return self.resultdef traversal(self, node, depth):if not node.left and not node.right:if depth > self.max_depth:self.max_depth = depthself.result = node.valreturnif node.left:self.traversal(node.left, depth+1)if node.right:self.traversal(node.right, depth+1)

递归的另一种写法，由ChatGPT提供

路径总和

Key Points

叶子节点是指没有子节点的节点。

相关题目

112. 路径总和
113. 路径总和ii

视频讲解

路径总和

重点分析

112
方法一：递归

def hasPathSum(root: TreeNode, targetSum: int) -> bool:if not root:return False# 更新目标和targetSum -= root.val# 如果是叶子节点，检查目标和是否为0if not root.left and not root.right:return targetSum == 0# 递归遍历左右子节点return hasPathSum(root.left, targetSum) or hasPathSum(root.right, targetSum)

方法二：迭代法

def hasPathSum(root, targetSum):if not root:return Falsestack_record = [(root, root.val)]while stack_record:node, value = stack_record.pop()if not node.left and not node.right:if value == targetSum:return Trueelse:if node.right:stack_record.append((node.right, value+node.right.val))if node.left:stack_record.append((node.left, value + node.left.val))return False

113 方法一：递归法

class Solution:def pathSum(self, root: TreeNode, targetSum: int) -> [[int]]:result = []self.dfs(root, targetSum, [], result)return resultdef dfs(self, node, targetSum, path, result):if not node:return# 添加当前节点到路径path.append(node.val)# 检查是否是叶子节点且路径总和等于目标和if not node.left and not node.right and sum(path) == targetSum:result.append(list(path))else:# 递归遍历左右子节点self.dfs(node.left, targetSum, path, result)self.dfs(node.right, targetSum, path, result)# 回溯前去除当前节点path.pop()# 示例使用
# 假设有一个二叉树和目标和，可以创建TreeNode实例并调用Solution().pathSum(root, targetSum)来获取结果

方法二：迭代法

def pathSum(root, targetSum):if not root:return []stack_record = [(root, [root.val])]res = []while stack_record:node, value_list = stack_record.pop()if not node.left and not node.right:if sum(value_list) == targetSum:res.append(value_list)else:if node.right:stack_record.append((node.right, value_list+[node.right.val]))if node.left:stack_record.append((node.left, value_list + [node.left.val]))return res