求二叉树上各条路径上的值的和
时间: 2024-05-13 09:18:49 浏览: 10
可以使用递归来求解二叉树上各条路径上的值的和。对于每一个节点,我们可以把它的值加入到路径上,然后递归地计算其左子树和右子树上的路径和。最终,我们把左子树和右子树的路径和加起来,就是从该节点出发的所有路径的和。
具体实现如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def pathSum(root: TreeNode) -> int:
if not root:
return 0
return pathSumRec(root, 0)
def pathSumRec(node: TreeNode, sum_so_far: int) -> int:
if not node:
return 0
sum_so_far += node.val
if not node.left and not node.right: # 叶子节点
return sum_so_far
return pathSumRec(node.left, sum_so_far) + pathSumRec(node.right, sum_so_far)
```
在主函数中,我们调用 `pathSum` 函数来求解二叉树上所有路径的和。如果根节点为空,那么路径和为0。否则,我们调用 `pathSumRec` 函数来计算从根节点出发的所有路径的和。初始时,路径和为0。`pathSumRec` 函数首先将当前节点的值加入到路径和中,然后递归地调用其左子树和右子树,分别计算左子树和右子树的路径和。如果当前节点是叶子节点,则返回从根节点到该叶子节点的路径和。最终,我们将左子树和右子树的路径和相加,就是从该节点出发的所有路径的和。
注意,上述实现中,我们每次递归都创建了一个新的变量 `sum_so_far` 来存储路径和。实际上,我们可以把 `sum_so_far` 作为函数参数来传递,这样可以避免创建新变量的开销。