LeetCode 113. 路径总和 II

Categories:

Tags:

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

题目描述

✅ 113. 路径总和 II

思路分析

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

核心思路：

从根节点出发进行 DFS，维护当前路径与剩余目标值。

到达叶子节点且剩余值为 0 时记录路径。

回溯时撤销路径选择。

复杂度分析：

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

空间复杂度：O(h)，其中 h 表示树高度，递归栈与路径数组占用。

import java.util.*;

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(root, targetSum, path, res);
        return res;
    }

    private void dfs(TreeNode node, int remain, List<Integer> path, List<List<Integer>> res) {
        if (node == null) {
            return;
        }

        path.add(node.val);
        int next = remain - node.val;

        if (node.left == null && node.right == null && next == 0) {
            res.add(new ArrayList<>(path));
        } else {
            dfs(node.left, next, path, res);
            dfs(node.right, next, path, res);
        }

        path.remove(path.size() - 1);
    }
}

func pathSum(root *TreeNode, targetSum int) [][]int {
	res := make([][]int, 0)
	path := make([]int, 0)

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

		path = append(path, node.Val)
		remain -= node.Val

		if node.Left == nil && node.Right == nil && remain == 0 {
			tmp := make([]int, len(path))
			copy(tmp, path)
			res = append(res, tmp)
		} else {
			dfs(node.Left, remain)
			dfs(node.Right, remain)
		}

		path = path[:len(path)-1]
	}

	dfs(root, targetSum)
	return res
}

相似题目

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

本文作者: HGNULB

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