112. Path Sum
給定一棵二元樹的根節點和一個整數目標和（targetSum），如果存在從根節點到葉節點的路徑，其路徑上所有節點值的總和等於目標和，則返回 true。
葉節點是沒有子節點的節點。
範例：
輸入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 輸出：true 解釋：符合目標和的根到葉節點的路徑如圖所示。
Python
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
# Check if we have reached a leaf node
if not root.left and not root.right:
return targetSum == root.val
# Recursively check the left and right subtrees
return (self.hasPathSum(root.left, targetSum - root.val) or
self.hasPathSum(root.right, targetSum - root.val))
17.5MB, 44ms
C++
#include <iostream>
using namespace std;
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) {
return false;
}
// Check if we have reached a leaf node
if (!root->left && !root->right) {
return targetSum == root->val;
}
// Recursively check the left and right subtrees
return hasPathSum(root->left, targetSum - root->val) ||
hasPathSum(root->right, targetSum - root->val);
}
};
19.73MB, 4ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val === undefined ? 0 : val)
* this.left = (left === undefined ? null : left)
* this.right = (right === undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {boolean}
*/
var hasPathSum = function(root, targetSum) {
if (root === null) {
return false;
}
// Check if we have reached a leaf node
if (root.left === null && root.right === null) {
return targetSum === root.val;
}
// Recursively check the left and right subtrees
return hasPathSum(root.left, targetSum - root.val) ||
hasPathSum(root.right, targetSum - root.val);
};
51.36MB, 62ms
