Leetcode No.437 路径总和 二叉树 回溯法

题目大意

给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

image.png

方法：递归法

 public int pathSum(TreeNode root, int sum) {
        if(root==null) return 0;
        return paths(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum);
    }

private int paths(TreeNode root,int sum) {
        if(root == null) return 0;
        int res = 0;
        if(root.val == sum) 
            res += 1;
        res += paths(root.left,sum-root.val);
        res += paths(root.right,sum-root.val);
        return res;
    } 

运行时间17ms，77.24%。