026 · Path Sum

Problem

给定一棵二叉树的根节点 root，以及一个整数 targetSum。

请判断这棵树中是否存在一条从根节点到叶子节点的路径，使得这条路径上所有节点的值加起来正好等于 targetSum。

如果存在这样的路径，返回 True；否则返回 False。

叶子节点是没有左孩子、也没有右孩子的节点。

例如，下面这棵树中存在一条路径的和等于 22：

        5
       / \
      4   8
     /   / \
    11  13  4
   /  \      \
  7    2      1

路径是：

5 -> 4 -> 11 -> 2

这些节点的值相加为：

5 + 4 + 11 + 2 = 22

所以答案是 True。

注意，路径必须从根节点开始，并且必须走到叶子节点才算完整。不能只走到中间某个节点就停止。

Examples

示例 1

Input:  root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: True

解释：存在一条路径 5 -> 4 -> 11 -> 2，节点值之和是 22。

示例 2

Input:  root = [1,2,3], targetSum = 5
Output: False

解释：从根节点到叶子节点的路径只有 1 -> 2 和 1 -> 3，它们的和分别是 3 和 4，都不等于 5。

示例 3

Input:  root = [], targetSum = 0
Output: False

解释：空树中没有任何根到叶子节点的路径。

Constraints

• 树中节点的数量范围是 \([0, 5000]\)
• \(-1000 \leq\) Node.val \(\leq 1000\)
• \(-1000 \leq\) targetSum \(\leq 1000\)

Link

• Original Problem

---

→ Solution