leetcode-path-sum-iii

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/path-sum-iii/

　　让你输出二叉树中路径和为sum的路径个数，这里的“路径”指的是自上而下的路径就可以，路径的起点不一定是根节点，终点也不一定是叶子节点。

https://ooo.0o0.ooo/2016/11/20/583182bf04877.png

题目分析

　　注意一条路径的起点和终点不一定是树根和叶子节点，helper方法完成了从当前节点向下的路径中所有的和为sum，因此对树的每个节点都执行一次helper方法，再求其总和就是答案。

代码

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
30
31
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    public int helper(TreeNode root, int sum) {
        int ans = 0;
        if(root == null) {
            return ans;
        }
        if(sum == root.val) {
            ans++;
        }
        ans += helper(root.left, sum - root.val);
        ans += helper(root.right, sum - root.val);
        return ans;
    }
    
    public int pathSum(TreeNode root, int sum) {
        if(root == null) {
            return 0;
        }
        return helper(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
}

　　时间复杂度待分析~