437. Path Sum III

Leetcode 链接

题目

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

题意解析

判断二叉树中是否存在路径，该路径上所有节点的和为指定值。求这样的路径总数。

解决方案

• 需要注意的是，路径的起点未必是根节点，终点未必是叶子节点
• 我的做法比较粗暴：将每个节点作为根节点去判断。应该有更好的办法，待改进。

Go 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func pathSum(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    }

    res := 0
    helper(root, 0, &sum, &res)

    return res + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}

func helper(root *TreeNode, currentSum int, sum, res *int) {
    if root == nil {
        return
    }

    currentSum += root.Val
    if currentSum == *sum {
        *res += 1
    }

    helper(root.Left, currentSum, sum, res)
    helper(root.Right, currentSum, sum, res)
}