递归在树中的应用（leetcode题）
来源：3-4 关于Leetcode的更多说明
payzul
2020-04-17
题目：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null && root.val == sum) {
return true;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum -root.val);
}
老师你好：
leetcode上刷题，我还是有点不理解递归在这里的应用。这里是如何做到
root.val == sum 就相当于相加了所有节点呢？
此外 为什么要 sum - root.val 呢？ 是因为root.left 进一步递归，所以要去除该节点么?
谢谢！
2回答
-
hasPathSum(TreeNode root, int sum) 的语义是，判断从当前的节点 root，到某个叶子节点，是否有和为 sum 的路径。
if (root.left == null && root.right == null && root.val == sum) {
return true;
}的意思是，如果 root 本身已经是叶子节点了，那么如果 root.val == sum，我们就已经找到这样一个路径了。这个路径只有一个节点，就是 root。
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum -root.val);
的意思是，否则的话，我们就把当前的这个 root 的值抛去，看从 root.left 出发，或者从 root.right 出发，有没有和是 sum - root.val 的路径，如果有，那么加上当前这个 root 本身，就构成了一个和为 sum 的路径。
我建议你至少学完这个课程介绍链表的过程中，所讲解的递归的微观解读。然后再仔细分析一下这个程序。要注意，每次递归函数调用的 root 和 sum 到底是谁。他们的值是在改变的。
继续加油！：）
122020-04-18 -
自然妙有猫仙人
2020-04-18
这个算法本质就是个前序遍历
计算的就是root.val+左子树sum或root.val + 右子树sum的值是否等于目标sum
在计算子树的目标sum前需要先sum - root.val得到正确的子树目标sum值，因为root不在子树需要计算的范围内
这样递归到叶子节点后，就是
if (root.left == null && root.right == null && root.val == sum) {
return true;
}所判断的情况
此时判断root.val是否等于sum即可
122020-04-18
相似问题