LeetCode 113. 路径总和 II

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 113. 路径总和 II

思路分析

递归遍历：使用深度优先搜索遍历二叉树，从根节点开始，逐层向下，直到叶子节点。

记录路径：在遍历过程中，记录当前路径上的节点值。

判断叶子节点：当到达叶子节点时，检查当前路径的和是否等于目标和。如果是，则将当前路径添加到结果中。

回溯：在返回上层节点时，移除当前节点，以便于探索其他路径。

参考代码

func pathSum(root *TreeNode, targetSum int) [][]int {
	var res [][]int
	var path []int

	var dfs func(node *TreeNode, sum int)
	dfs = func(node *TreeNode, sum int) {
		if node == nil {
			return
		}

		// 将当前节点加入路径
		path = append(path, node.Val)
		sum -= node.Val

		// 如果是叶子节点，且路径和刚好等于 targetSum
		if node.Left == nil && node.Right == nil && sum == 0 {
			res = append(res, append([]int{}, path...))
		}

		// 递归左右子树
		dfs(node.Left, sum)
		dfs(node.Right, sum)

		// 回溯，移除最后一个元素
		path = path[:len(path)-1]
	}

	dfs(root, targetSum)
	return res
}

func pathSum(root *TreeNode, targetSum int) [][]int {
	var res [][]int
	var path []int

	var dfs func(cur *TreeNode, curSum int)
	dfs = func(cur *TreeNode, curSum int) {
		if cur == nil {
			return
		}
		// 将当前节点的值添加到路径中
		path = append(path, cur.Val)
		curSum += cur.Val

		// 如果是叶子节点，检查路径和是否等于目标值
		if cur.Left == nil && cur.Right == nil {
			if curSum == targetSum {
				res = append(res, append([]int{}, path...))
			}
		} else {
			// 继续遍历左子树和右子树
			dfs(cur.Left, curSum)
			dfs(cur.Right, curSum)
		}

		// 回溯，移除当前节点
		path = path[:len(path)-1]
	}

	dfs(root, 0)
	return res
}

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/58259664