leetcode_437

发表于   |   分类于

Path Sum III

题目戳这

题意

给一颗二叉树，然后给定一个值sum，求有多少种路径，使得 node[i] + node[i+1] + ...node[p] = sum,其中从i到p的点在二叉树上要连续，并且是从上而下。

解法

dfs的题目还是有点不太会写。对于这道题目来说，基本的想法就是我们对于树中的每一个节点都当做是根节点了来遍历它下面的所有子节点。所以我们其实有两个函数都用到了递归的思想。
主函数就是不断递归每个点，然后将其作为根节点放入另外一个递归中进行计算，看是否有符合条件的连续子序列的和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 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 dfs(self, root, sum):
        num = 0
        if not root:
            return num
        if sum == root.val: # 符合条件
            num += 1
        num += self.dfs(root.left, sum-root.val) # 递归左子树
        num += self.dfs(root.right, sum-root.val) # 递归右子树
        return num
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        if not root:
            return 0
        
        # 将这棵树上的每个节点当做根节点来计算其子序列的和
        return self.dfs(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)