112. 路径总和
题目描述
输入二叉树的根节点 root 和一个整数 targetSum。
考虑所有从根出发、一直走到某个叶子节点的路径。叶子节点指没有任何孩子的节点。只要有一条这样的路径，其节点值之和恰好为 targetSum，就返回 true；一条都没有就返回 false。
空树里不存在任何路径，返回 false。树用层序数组表示，null 代表空位。
示例 1
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1] targetSum = 22 输出：true
解释：路径 5 -> 4 -> 11 -> 2 的和为 22。
示例 2
输入：root = [1,2,3], targetSum = 5 输出：false
解释：两条根到叶子的路径和分别为 3 和 4，都不是 5。
示例 3
输入：root = [], targetSum = 0 输出：false
解释：树为空，没有路径可选。
数据范围
- 节点总数在
[0, 5000]之间。 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
解题思路：递归深度优先搜索
每往下走一个节点，就把它的值从 targetSum 里减掉，问题变成“子树里是否有一条路径和等于剩下的数”。走到叶子时，剩余值恰好为 0 就说明找到了。左子树找到就直接返回 True，借助 or 的短路不再搜索右子树。
为什么正确
调用 hasPathSum(node, t) 时，t 等于原 targetSum 减去从根到 node 父节点的路径和。
复杂度分析
时间 O(n)，空间 O(h)，h 为树高。
易错点
只能在叶子处判断剩余值是否为 0。如果在空节点处判断，一个只有一侧孩子的节点会把“空的那一侧”误当作路径终点。另外节点值可能为负，不能在剩余值小于 0 时提前剪枝。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
targetSum -= root.val
if not root.left and not root.right:
return targetSum == 0
return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
targetSum -= root.val;
if (root.left == null && root.right == null) {
return targetSum == 0;
}
return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
}
}class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) {
return false;
}
targetSum -= root->val;
if (!root->left && !root->right) {
return targetSum == 0;
}
return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
}
};func hasPathSum(root *TreeNode, targetSum int) bool {
if root == nil {
return false
}
targetSum -= root.Val
if root.Left == nil && root.Right == nil {
return targetSum == 0
}
return hasPathSum(root.Left, targetSum) || hasPathSum(root.Right, targetSum)
}var hasPathSum = function(root, targetSum) {
if (!root) {
return false;
}
targetSum -= root.val;
if (!root.left && !root.right) {
return targetSum === 0;
}
return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
};function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
if (!root) {
return false;
}
targetSum -= root.val;
if (!root.left && !root.right) {
return targetSum === 0;
}
return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
}其他解法
递归把剩余目标值传给子树，代码最短；广度优先搜索把路径和和节点一起入队，空间随层宽变化。
解法 2：广度优先搜索 时间 O(n)，空间 O(w)
队列里同时保存节点和从根到它的路径和。弹出节点时，如果它是叶子并且路径和等于 targetSum，就返回 true。否则把子节点连同累加后的路径和入队。
没有递归，深链树不会栈溢出。需要额外保存每个待处理节点的路径和，代码比递归长。
from collections import deque
class Solution:
def hasPathSum(self, root, targetSum):
if not root:
return False
queue = deque([(root, root.val)])
while queue:
node, s = queue.popleft()
if not node.left and not node.right and s == targetSum:
return True
if node.left:
queue.append((node.left, s + node.left.val))
if node.right:
queue.append((node.right, s + node.right.val))
return Falseclass Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
Deque<TreeNode> nodes = new ArrayDeque<>();
Deque<Integer> sums = new ArrayDeque<>();
nodes.offer(root);
sums.offer(root.val);
while (!nodes.isEmpty()) {
TreeNode node = nodes.poll();
int s = sums.poll();
if (node.left == null && node.right == null && s == targetSum) return true;
if (node.left != null) {
nodes.offer(node.left);
sums.offer(s + node.left.val);
}
if (node.right != null) {
nodes.offer(node.right);
sums.offer(s + node.right.val);
}
}
return false;
}
}class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) return false;
queue<pair<TreeNode*, int>> q;
q.push({root, root->val});
while (!q.empty()) {
auto [node, s] = q.front(); q.pop();
if (!node->left && !node->right && s == targetSum) return true;
if (node->left) q.push({node->left, s + node->left->val});
if (node->right) q.push({node->right, s + node->right->val});
}
return false;
}
};func hasPathSum(root *TreeNode, targetSum int) bool {
if root == nil {
return false
}
type item struct {
node *TreeNode
sum int
}
queue := []item{{root, root.Val}}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
node, s := cur.node, cur.sum
if node.Left == nil && node.Right == nil && s == targetSum {
return true
}
if node.Left != nil {
queue = append(queue, item{node.Left, s + node.Left.Val})
}
if node.Right != nil {
queue = append(queue, item{node.Right, s + node.Right.Val})
}
}
return false
}var hasPathSum = function(root, targetSum) {
if (!root) return false;
const queue = [[root, root.val]];
for (let i = 0; i < queue.length; i++) {
const [node, s] = queue[i];
if (!node.left && !node.right && s === targetSum) return true;
if (node.left) queue.push([node.left, s + node.left.val]);
if (node.right) queue.push([node.right, s + node.right.val]);
}
return false;
};function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
if (!root) return false;
const queue: [TreeNode, number][] = [[root, root.val]];
for (let i = 0; i < queue.length; i++) {
const [node, s] = queue[i];
if (!node.left && !node.right && s === targetSum) return true;
if (node.left) queue.push([node.left, s + node.left.val]);
if (node.right) queue.push([node.right, s + node.right.val]);
}
return false;
};