437. 路径总和 III

这题使用dfs,做两层递归即可/** * 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 { //1️⃣ pathSum枚举每一个节点作为“起点” //2️⃣ rootSum从这个起点往下找路径和 target public int pathSum(TreeNode root, int targetSum) { if (root null) { return 0; } int ret rootSum(root, targetSum); ret pathSum(root.left, targetSum); ret pathSum(root.right, targetSum); return ret; } public int rootSum(TreeNode root, long targetSum) { int ret 0; if (root null) { return 0; } int val root.val; if (val targetSum) { ret; } ret rootSum(root.left, targetSum - val); ret rootSum(root.right, targetSum - val); return ret; } }