郑州品牌网站建设费用,金华网站建设明细报价表,网站前台修改,中国建设银行怎么添加卡网站相关推荐 python coding with ChatGPT 打卡第12天| 二叉树#xff1a;理论基础 python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历 python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历 python coding with ChatGPT 打卡第15天| 二叉树#xff1a;翻转…相关推荐 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相关题目视频讲解重点分析 路径总和Key Points相关题目视频讲解重点分析 找树左下角的值
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 i0: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, depth1)if node.right:self.traversal(node.right, depth1)
递归的另一种写法由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, valuenode.right.val))if node.left:stack_record.append((node.left, value node.left.val))return False113 方法一递归法
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
