112.md

112. 路径总和

      ⑤
     / \
    ④   8
   /    / \
  ⑪   13  4
 /  \      \
7    ②      1

思路

• 使用 || 来判断左右子节点
• 减去每一层的值，到叶子节点时，如果减去叶子节点值刚好为 0，则符合。
• 必须遍历完路径所有节点，才能知道此路径是否符合。如果没有符合路径，树所有节点均会判断；如果有，不再调用递归，可提前结束。
• 时间复杂度：O(n)，n 为节点的数量 + 叶子节点的 null 子节点。此时为最坏时间复杂度
• 空间复杂度：O(n)，n 为递归次数，额外需要一个 sum 变量
• 标签：

思路转代码

• 判断结束条件最难！

代码

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        // 如何节点为 null，代表是叶子节点的左右节点。用于结束到叶子节点后，还不符合条件的场景。如果没有路径符合的结束条件。
        if (root == null) {
            return false;
        }
        sum = sum - root.val;
        if (root.left == null && root.right == null) {
            return sum == 0;
        }
        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    }
}

错误代码

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        // 不能通过 sum == 0 来判断，如果中途为 0，则错误
        if (root == null && sum == 0) {
            return false;
        }
        if (root == null && sum != 0) {
            return false;
        }
        if (root != null && sum == 0) {
            return false;
        }
        sum = sum - root.val;
        if (sum == 0 && root.left == null && root.right == null) {
            return true;
        }
        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    }
}

测试用例

[5,4,8,11,null,13,4,7,2,null,null,null,1]
22

[]
0

[1,-2,-3,1,3,-2,null,-1]
-1

1 + -2 + 1 + -1 = -1