LeetCode 112. 路径总和

Categories:

Tags:

题目描述
思路分析
1. 解法一：深度优先搜索（推荐）
相似题目

题目描述

✅ 112. 路径总和

思路分析

解法一：深度优先搜索（推荐）

核心思路：

从根节点出发，逐层减去当前节点值。

到叶子节点时判断剩余值是否为 0。

任意路径满足即可返回 true。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数量。

空间复杂度：O(h)，其中 h 表示树高度。

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }

        int remain = targetSum - root.val;
        return hasPathSum(root.left, remain) || hasPathSum(root.right, remain);
    }
}

func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}
	if root.Left == nil && root.Right == nil {
		return targetSum == root.Val
	}

	remain := targetSum - root.Val
	return hasPathSum(root.Left, remain) || hasPathSum(root.Right, remain)
}

相似题目

题目	难度	考察点
113. 路径总和 II	中等	DFS
129. 求根节点到叶节点数字之和	中等	DFS
257. 二叉树的所有路径	简单	DFS
437. 路径总和 III	中等	DFS
404. 左叶子之和	简单	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/60277569