网站配色与布局,类似卡盟网站卖怎么做,网页设计代码的基本格式,Wordpress屏蔽国内iip目录
解法#xff1a;
官方解法#xff1a;
方法一#xff1a;广度优先搜索
思路及算法
复杂度分析
时间复杂度#xff1a;
空间复杂度#xff1a;
方法二#xff1a;递归
思路及算法
复杂度分析
时间复杂度#xff1a;
空间复杂度#xff1a; 给你二叉树的…目录
解法
官方解法
方法一广度优先搜索
思路及算法
复杂度分析
时间复杂度
空间复杂度
方法二递归
思路及算法
复杂度分析
时间复杂度
空间复杂度 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false 。
叶子节点 是指没有子节点的节点。 示例 1 输入root [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum 22
输出true
解释等于目标和的根节点到叶节点路径如上图所示。示例 2 输入root [1,2,3], targetSum 5
输出false
解释树中存在两条根节点到叶子节点的路径
(1 -- 2): 和为 3
(1 -- 3): 和为 4
不存在 sum 5 的根节点到叶子节点的路径。
示例 3
输入root [], targetSum 0
输出false
解释由于树是空的所以不存在根节点到叶子节点的路径。提示
树中节点的数目在范围 [0, 5000] 内-1000 Node.val 1000-1000 targetSum 1000
解法
同样使用深度优先遍历的方法将每个叶子节点的路径值相加起来。
/*** 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 boolean hasPathSum(TreeNode root, int targetSum) {int[] judge {0};hasNextNode(root, targetSum, 0, judge);return judge[0] 1;}public void hasNextNode(TreeNode root, int targetSum, int rNum, int[] judge) {if (root null) {return;}//将当前节点的值与上一节点的值添加起来rNum root.val;//1.遍历左边hasNextNode(root.left, targetSum, rNum, judge);//2.遍历右边hasNextNode(root.right, targetSum, rNum, judge);//当遍历到叶子节点时判断是否符合targetSumif (root.left null root.right null) {//判断是否符合targetSumif (rNum targetSum) {judge[0] 1;}}}
} 官方解法
方法一广度优先搜索
思路及算法
首先我们可以想到使用广度优先搜索的方式记录从根节点到当前节点的路径和以防止重复计算。
这样我们使用两个队列分别存储将要遍历的节点以及根节点到这些节点的路径和即可。
class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root null) {return false;}QueueTreeNode queNode new LinkedListTreeNode();QueueInteger queVal new LinkedListInteger();queNode.offer(root);queVal.offer(root.val);while (!queNode.isEmpty()) {TreeNode now queNode.poll();int temp queVal.poll();if (now.left null now.right null) {if (temp sum) {return true;}continue;}if (now.left ! null) {queNode.offer(now.left);queVal.offer(now.left.val temp);}if (now.right ! null) {queNode.offer(now.right);queVal.offer(now.right.val temp);}}return false;}
}
复杂度分析
时间复杂度
O(N)其中 N 是树的节点数。对每个节点访问一次。
空间复杂度
O(N)其中 N 是树的节点数。空间复杂度主要取决于队列的开销队列中的元素个数不会超过树的节点数。
方法二递归
思路及算法
观察要求我们完成的函数我们可以归纳出它的功能询问是否存在从当前节点 root 到叶子节点的路径满足其路径和为 sum。
假定从根节点到当前节点的值之和为 val我们可以将这个大问题转化为一个小问题是否存在从当前节点的子节点到叶子的路径满足其路径和为 sum - val。
不难发现这满足递归的性质若当前节点就是叶子节点那么我们直接判断 sum 是否等于 val 即可因为路径和已经确定就是当前节点的值我们只需要判断该路径和是否满足条件。若当前节点不是叶子节点我们只需要递归地询问它的子节点是否能满足条件即可。
class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root null) {return false;}if (root.left null root.right null) {return sum root.val;}return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);}
}
复杂度分析
时间复杂度
O(N)其中 N 是树的节点数。对每个节点访问一次。
空间复杂度
O(H)其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销最坏情况下树呈现链状空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关空间复杂度为 O(logN)。 官方解法部分
作者力扣官方题解链接https://leetcode.cn/problems/path-sum/ 来源力扣LeetCode
