437.路径总和III

题目描述

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例

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

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

返回 3。和等于 8 的路径有:

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

思路

1. 既然题目中说明不超过1000个结点，可以使用一个长度为1000的数组，用于保存所有结点的值。
2. 可以抽象理解为vals[0]是vals[1]的父节点，vals[1]是vals[2]的父节点。
3. 一个结点的路径总和为：rootNum = rootNum + leftNum + rightNum。
4. 可以使用递归来处理求和，递归到某一结点时，自底向上的相加结点求和与target即可。

Java代码实现

class Solution {
    private int num = 0;
    public int pathSum(TreeNode root, int sum) {
        int[] vals = new int[1000];

        return pathSumDS(root,0,vals,sum);
    }

    private int pathSumDS(TreeNode root,int depth,int[] vals,int sum){
        if(root == null)
            return 0;
        int rootVal = root.val;

        int num = 0;
        if(rootVal == sum){
            num = 1;
        }

        for(int i=depth-1;i>=0;i--){
            rootVal = rootVal + vals[i];
            if(rootVal == sum){
                num++;
            }
        }
        vals[depth] = root.val;

        int left = pathSumDS(root.left,depth+1,vals,sum);
        int right = pathSumDS(root.right,depth+1,vals,sum);

        return num+left+right;
    }
}

Golang代码实现

func pathSum(root *TreeNode, sum int) int {
    vals := make([]int,1000)
    return pathSumDS(root,sum,0,vals)
}

func pathSumDS(root *TreeNode, sum int, depth int,vals []int) int {
    if root == nil{
        return 0
    }

    rootVal := root.Val
    num := 0

    if rootVal == sum{
        num++
    }

    for i:=depth-1;i>=0;i--{
        rootVal += vals[i]
        if rootVal == sum{
            num++
        }
    }

    vals[depth] = root.Val

    left := pathSumDS(root.Left,sum,depth+1,vals)
    right := pathSumDS(root.Right,sum,depth+1,vals)

    return num+left+right
}