112. 路径总和
题意:给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。
叶子节点 是指没有子节点的节点。
解题思路
解法1:递归
1.假设当前节点为k,根节点到当前节点的和为val,那么如果有叶子节点满足targetSum的话,一定满足条件:根节点到当前节点的和==targetSum-当前节点的下一节点到叶子节点的和
2.递归还有一个重要条件需要找到,即结束条件,我们知道叶子节点的判断条件为:root.left == null && root.right == null
3.由1推导可知,如果此时的叶子节点满足条件,一定满足条件current.val == vSum
,这里的vSum实际上前面targetSum一直在递归过程中,减去叶子节点之前的节点的差,即vSum=targetSum-current上面所有节点值
解题遇到的问题
无
后续需要总结学习的知识点
需要深入总结学习DFS/BFS/递归/迭代 与队列、栈的相互关系
##解法1
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return root.val == targetSum;
}
return hasPathSum(root.left, targetSum - root.val)
|| hasPathSum(root.right, targetSum - root.val);
}
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;
}
}
}
网友评论