OJ练习第142题——路径总和 II

**路径总和 II**

**题目描述**

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

**示例1:**

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

输出：`37`

解释：返回 `3 ->9 ->20 -> null`, `3 ->9 ->15 -> null`, `3 ->9 ->7 -> null` 这三条路径的总和。

**示例2:**

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

输出：`24`

解释：返回 `-10 ->9 ->20 -> null`, `-10 ->9 ->15 -> null`, `-10 ->9 ->7 -> null` 这三条路径的总和。

**示例3:**

输入：`[1,2,3,4,5,6,7]`

输出：`28`

解释：返回 `1 ->2 ->3 ->4 ->5 ->6 ->7` 这一条路径的总和。

**解决方案**

我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决这个问题。这里，我们选择使用 DFS。

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef pathSum(root: TreeNode) -> int:
 """
 :param root: 二叉树的根节点 :return: 所有从根到叶子结点的路径之和 """
 # 如果二叉树为空，则返回0 if not root:
 return0 # 初始化结果变量 result =0 # 定义一个函数来计算从当前节点到叶子结点的路径之和 def dfs(node, path_sum):
 nonlocal result # 如果当前节点为空，则返回 if not node:
 return # 将当前节点的值加到路径之和中 path_sum += node.val # 如果当前节点是叶子结点，则更新结果变量 if not node.left and not node.right:
 result += path_sum # 递归计算左子树和右子树的路径之和 dfs(node.left, path_sum)
 dfs(node.right, path_sum)
 # 开始 DFS dfs(root,0)
 # 返回结果变量 return result# 测试代码root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

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