76. LeetCode.437. 路径总和 III

• 标签： 树
• 难度： 简单

• 题目描述

• 我的解法

这道题与 LeetCode 112. 路径总和 和 LeetCode.113. 路径总和 II 不同， 路径起点不一定是根节点，路径终点不一定是叶子结点. 所以原来的递归出口条件需要放松. 增添了一个辅助函数 rootSum(root, sum) 返回以 root 为起点的（同样， 路径终点不一定是叶子结点）, 路径和为 sum 的路径数.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def rootSum(self, root, sum):
        result = 0
        if not root:
            return result
        if root.val == sum:
            result += 1
            
        result += self.rootSum(root.left, sum - root.val)
        result += self.rootSum(root.right, sum - root.val)
        return result
    
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        result = 0
        if not root:
            return result
        result += self.rootSum(root,  sum)
        result += self.pathSum(root.left, sum)
        result += self.pathSum(root.right, sum)
        return result

• 其他解法

暂略。