2025/10/16

思路：二叉树肯定是要递归遍历的。我写了一个最暴力的解法，直接统计从每个节点出发的符合条件的路径数目，然后全加起来。每个节点出发的路径数目，用回溯法，但是不带剪枝。


def DFS(T):
    count_left = DFS(T.left)
    count_right = DFS(T.right)
    count_itself = count_begin(T, value =0)
    count = count_left + count_right + count_itself
    return count

def count_begin(T, value):
    count = 0
    value += T.value
    if value == target:
        count += 1
    count += count_begin(T.left, value)
    count += count_begin(T.right, value)

    return count

result = DFS(T)

评价：完全正确，只是说这个题是比较麻烦的，而且就该用麻烦的办法做