上海网站建设定,自己做网站挂广告怎么赚钱,网页设计与网站建设课程考试,商贸公司寮步网站建设文章目录题目描述思路 代码题目描述
说实话确实比I II要恶心一点这里直接用双递归秒了#xff08;今天才发现我是之前先写的III#xff0c;再写的I II#xff09;有前缀和的写法#xff0c;但是懒得整了
思路 代码
和之前不同#xff0c;这里…
文章目录题目描述思路 代码题目描述
说实话确实比I II要恶心一点这里直接用双递归秒了今天才发现我是之前先写的III再写的I II有前缀和的写法但是懒得整了
思路 代码
和之前不同这里对起点、终点不要求是根和叶子只要求路径向下。分成两种情况递归路径包含当前结点路径不包含当前结点。
/*** 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 {int ans 0;public int pathSum(TreeNode root, int targetSum) {if(root null){return 0;}// 不算 root 在内的左右可行的情况pathSum(root.right, targetSum);pathSum(root.left, targetSum);// 算 root 在内的bfs(root, targetSum, 0);return ans;}void bfs(TreeNode root, int targetSum, int nowNum){if(root null){return;}nowNum root.val;if(nowNum targetSum){ans;}bfs(root.left, targetSum, nowNum);bfs(root.right, targetSum, nowNum);}
}无注释版
class Solution {int ans 0;public int pathSum(TreeNode root, int targetSum) {if(root null) {return 0;}pathSum(root.left, targetSum);pathSum(root.right, targetSum);find(root, targetSum);return ans;}public void find(TreeNode root, int targetSum) {if(root null) {return;}if(root.val targetSum) {ans;}find(root.left, targetSum - root.val);find(root.right, targetSum - root.val);}
}
