益阳网站建设广告,小浪底水利枢纽建设管理局网站,wordpress夜间模式插件,yy头像在线制作网站【问题描述】[中等] 【解答思路】
1. 递归 时间复杂度#xff1a;O(N) 空间复杂度#xff1a;O(H) 从根节点开始#xff0c;每当遇到一个节点的时候#xff0c;从目标值里扣除节点值#xff0c;一直到叶子节点判断目标值是不是被扣完。
class Solution {public boolean…【问题描述】[中等] 【解答思路】
1. 递归 时间复杂度O(N) 空间复杂度O(H) 从根节点开始每当遇到一个节点的时候从目标值里扣除节点值一直到叶子节点判断目标值是不是被扣完。
class Solution {public boolean hasPathSum(TreeNode root, int sum) {if (root null) {return false;}if (root.left null root.right null) {// return sum-root.val0;return sum root.val;}return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);}
}
声明一个变量记录已经经过的节点的值之和每经过一个节点就加上这个节点的值在叶子节点判断变量值是否为目标值。 public boolean hasPathSum(TreeNode root, int sum) {return helper(root,0,sum);}public boolean helper(TreeNode root,int cur,int sum){if(rootnull)return false;curcurroot.val;if(root.leftnullroot.rightnull){return cursum;}else{return helper(root.left,cur,sum)|| helper(root.right,cur,sum);}}。2. 广度优先搜索 时间复杂度O(N) 空间复杂度O(N)
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;}
}
【总结】
1.注意事项 2.数的递归
树的递归题目是非常有套路可循的因为树有两个分支所以在递归里也有两个分支一般是通过 递归 A||递归 B 来实现分支的。只要明白了这一点递归函数就不会很难设计。
3.巧妙使用了两个队列 一个队列保存遍历节点 另一节点保存和
参考链接https://leetcode-cn.com/problems/path-sum/solution/lu-jing-zong-he-by-leetcode-solution/
参考链接https://leetcode-cn.com/problems/path-sum/solution/lu-jing-zong-he-jie-da-by-commonheart/
