1、解题思路

  1. 递归方法：从根节点开始递归遍历二叉树。每遍历到一个节点，将 sum 减去当前节点的值。如果当前节点是叶子节点且剩余 sum 为0，则返回 true。否则，递归检查左子树和右子树是否存在满足条件的路径。
  2. 迭代方法（DFS或BFS）：使用栈（DFS）或队列（BFS）进行遍历，同时记录路径的当前和。遇到叶子节点时，检查路径和是否等于 sum。

2、代码实现

C++（递归）
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        if (root == nullptr) {
            return false;
        }

        // 如果是叶子节点, 检查剩余 sum 是否等于当前节点的值
        if (root->left == nullptr && root->right == nullptr) {
            return sum == root->val;
        }

        // 递归检查左子树和右子树
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};
C++（迭代DFS）
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return bool布尔型
     */
    bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        if (root == nullptr) {
            return false;
        }

        stack<pair<TreeNode*, int>> s;
        s.push({root, sum});

        while (!s.empty()) {
            auto [node, curSum] = s.top();
            s.pop();
            // 到达叶子节点且路径和等于 sum
            if (node->left == nullptr && node->right == nullptr && curSum == node->val) {
                return true;
            }

            // 右子树入栈
            if (node->right != nullptr) {
                s.push({node->right, curSum - node->val});
            }

            // 左子树入栈
            if (node->left != nullptr) {
                s.push({node->left, curSum - node->val});
            }
        }

        return false;
    }
};
Java（递归）
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if (root == null) return false;
        
        // 如果是叶子节点，检查剩余 sum 是否等于当前节点的值
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        
        // 递归检查左子树和右子树
        return hasPathSum(root.left, sum - root.val) || 
               hasPathSum(root.right, sum - root.val);
    }
}
Python（递归）
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param sum int整型 
# @return bool布尔型
#
class Solution:
    def hasPathSum(self , root: TreeNode, sum: int) -> bool:
        # write code here
        if not root:
            return False
        
        # 如果是叶子节点，检查剩余 sum 是否等于当前节点的值
        if not root.left and not root.right:
            return sum == root.val
        
        # 递归检查左子树和右子树
        return self.hasPathSum(root.left, sum - root.val) or \
               self.hasPathSum(root.right, sum - root.val)
Python（迭代DFS）
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param sum int整型 
# @return bool布尔型
#
from collections import deque
class Solution:
    def hasPathSum(self , root: TreeNode, sum: int) -> bool:
        # write code here
        if not root:
            return False
        
        stack = deque([(root, sum)])
        
        while stack:
            node, curr_sum = stack.pop()
            
            # 到达叶子节点且路径和等于 sum
            if not node.left and not node.right and curr_sum == node.val:
                return True
            
            # 右子树入栈
            if node.right:
                stack.append((node.right, curr_sum - node.val))
            
            # 左子树入栈
            if node.left:
                stack.append((node.left, curr_sum - node.val))
        
        return False

3、复杂度分析

  • 时间复杂度：O(n)，每个节点被访问一次。
  • 空间复杂度：递归方法为 O(h)（树高），迭代方法为 O(n)（最坏情况下栈存储所有节点）。