113. 路径总和 II

**路径总和 II**

**题目描述**

给定一个二叉树的根节点，返回从根到叶子结点的所有路径之和。

**示例1:**

输入：`[3,9,20,null,pnull,15,7]`

输出：`72`

解释：最长路径为 `3 ->9 ->20 ->15 ->7`，总和为 `3 +9 +20 +15 +7 =54`。

**示例2:**

输入：`[1,2,3]`

输出：`6`

解释：最长路径为 `1 ->2 ->3`，总和为 `1 +2 +3 =6`。

**解决方案**

我们可以使用深度优先搜索（DFS）来遍历二叉树，并计算从根到叶子结点的所有路径之和。具体来说，我们可以使用递归函数来实现 DFS。

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef pathSum(root: TreeNode) -> int:
 """
 从根到叶子结点的所有路径之和。
 Args:
 root (TreeNode): 二叉树的根节点。
 Returns:
 int: 从根到叶子结点的所有路径之和。
 """
 if not root:
 return0 def dfs(node, sum):
 # 如果当前结点是叶子结点，则返回当前路径之和 if not node.left and not node.right:
 return sum + node.val # 递归计算左子树和右子树的路径之和 left_sum =0 right_sum =0 if node.left:
 left_sum = dfs(node.left, sum + node.val)
 if node.right:
 right_sum = dfs(node.right, sum + node.val)
 # 返回当前结点的路径之和 return max(left_sum, right_sum) if left_sum or right_sum else0 return dfs(root,0)

# 测试用例root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(pathSum(root)) # 输出:72