LeetCode 437. 路径总和

题目描述

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

思路

思路：递归

1. 方法pathSum中，我们知道可能的子路径为：从根节点出发的路径数量和+从根节点左子节点出发的路径数量和+从根节点右子节点出发的路径数量和
2. 路径和通过rootSum方法求解，递归终止条件为root == null，此时返回0；
3. rootSum方法中，获得root.val，如果root.val == target，则路径数量+1；到这里也不能返回，还要继续计算rootSum(root.left,targetSum-val)和rootSum(root.right,targetSum-val)的和；因为即使当前root.val == target使得目标和变为0，但仍有可能存在后面结果相加为0的情况（负数正数相加）

代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public long rootSum(TreeNode root, long targetSum) {long ret = 0;if (root == null) return 0;
//        if (targetSum == 0) return 0; // 考虑反例root=[0,1,1], targetSum=0// 这里都是算这个root节点的情况long val = root.val;if (val == targetSum) {ret++;}ret += rootSum(root.left, targetSum - val); // targetSum - val == 0了也不可以直接不递归，因为子结果中还可能存在后面相加结果为0的情况ret += rootSum(root.right, targetSum - val);return ret;}public int pathSum(TreeNode root, int targetSum) {// 终止条件if (root == null) return 0;// 可能的子路径为：根节点出发的路径和+左子节点出发的路径和+右子节点出发的路径和long ret = rootSum(root, targetSum); // 根节点出发的路径和ret += pathSum(root.left, targetSum); // 左子节点出发的路径和，这个过程中可能算左子节点，可能不算左子节点ret += pathSum(root.right, targetSum); // 右子节点出发的路径和，这个过程中可能算右子节点，可能不算右子节点return (int)ret;}
}