递归在树中的应用（leetcode题）

Question

题目：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
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 进一步递归，所以要去除该节点么?

谢谢！

Answer 1

liuyubobobo 2020-04-18 02:16:03

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 到底是谁。他们的值是在改变的。

继续加油！：）

• 提问者 payzul #1

  5
              4               8
       10
  7          3                                          
  
  目标值22.。  我一个个debug 了以下。root = 5 开始，会从当前节点一直遍历到叶子节点，至到递归条件退出。所以是每次减去当前root, 再最终root ==sum 来判定 前面遍历的节点总和 等于 sum的。

• 提问者 payzul #2

  非常感谢老师，我会继续加油的

Answer 2

自然妙有猫仙人 2020-04-18 00:17:22

这个算法本质就是个前序遍历

计算的就是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即可

• 提问者 payzul #1

  非常感谢同学的解答，我大概明白了 。 认为是需要认识递归特点：会从当前节点一直递归到  递归条件退出。

• 提问者 payzul #2

  我现在认为用好递归特性的关键是：设计好递归退出条件 和 业务满足需求时的 退出条件。 再把递归特性服务于业务要求（如题，需要递归减去，从而变向的验证路径之和 等于目标值。