题目描述

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

注意：叶子节点是指没有子节点的节点。

示例

给定如下二叉树和目标和 sum = 22：

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

返回 true，因为存在一条路径 5->4->11->2，其和为 22。

PHP 示例代码

<?php

class TreeNode {
    public $val;
    public $left;
    public $right;
    
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    /**
     * @param TreeNode $root
     * @param Integer $sum
     * @return Boolean
     */
    function hasPathSum($root, $sum) {
        if ($root === null) {
            return false;
        }
        
        // 如果到达叶子节点且当前路径和为目标和，则返回 true
        if ($root->left === null && $root->right === null && $root->val === $sum) {
            return true;
        }
        
        // 递归检查左子树和右子树
        return $this->hasPathSum($root->left, $sum - $root->val) || $this->hasPathSum($root->right, $sum - $root->val);
    }
}

// 示例用法
$root = new TreeNode(5);
$root->left = new TreeNode(4);
$root->right = new TreeNode(8);
$root->left->left = new TreeNode(11);
$root->left->left->left = new TreeNode(7);
$root->left->left->right = new TreeNode(2);
$root->right->left = new TreeNode(13);
$root->right->right = new TreeNode(4);
$root->right->right->right = new TreeNode(1);

$solution = new Solution();
$result = $solution->hasPathSum($root, 22);
echo $result ? 'true' : 'false'; // 输出 true

Python 示例代码

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: TreeNode, sum: int) -> bool:
        if not root:
            return False
        
        if not root.left and not root.right and root.val == sum:
            return True
        
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

# 示例用法
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
root.right.left = TreeNode(13)
root.right.right = TreeNode(4)
root.right.right.right = TreeNode(1)

solution = Solution()
result = solution.hasPathSum(root, 22)
print(result)  # 输出 True

JavaScript 示例代码

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var Solution = function() {};

Solution.prototype.hasPathSum = function(root, sum) {
    if (!root) {
        return false;
    }
    
    if (!root.left && !root.right && root.val === sum) {
        return true;
    }
    
    return this.hasPathSum(root.left, sum - root.val) || this.hasPathSum(root.right, sum - root.val);
};

// 示例用法
var root = new TreeNode(5);
root.left = new TreeNode(4);
root.right = new TreeNode(8);
root.left.left = new TreeNode(11);
root.left.left.left = new TreeNode(7);
root.left.left.right = new TreeNode(2);
root.right.left = new TreeNode(13);
root.right.right = new TreeNode(4);
root.right.right.right = new TreeNode(1);

var solution = new Solution();
var result = solution.hasPathSum(root, 22);
console.log(result); // 输出 true

在以上代码中，我们定义了二叉树的节点结构，并实现了 hasPathSum 函数来检查是否存在路径和为目标和的情况。通过递归地检查每个节点，我们可以找到满足条件的路径。