LeetCode 剑指 Offer 34. 二叉树中和为某一值的路径

Categories:

题目描述
思路分析
1. 解法一：回溯 DFS（推荐）
相似题目

题目描述

✅ 剑指 Offer 34. 二叉树中和为某一值的路径

思路分析

解法一：回溯 DFS（推荐）

核心思路：

从根节点出发，用 DFS 遍历所有从根到叶子节点的路径。

维护一个路径列表 path，每次进入节点时将当前节点值加入路径，同时将目标值减去当前节点值。

到达叶子节点时，若剩余目标值恰好为 0，说明当前路径满足条件，将其加入结果集。

递归返回时执行回溯，将路径末尾元素移除，恢复现场以探索其他分支。

复杂度分析：

时间复杂度：O(n²)，其中 n 是树中节点的数量。最坏情况下（满二叉树）需要将所有路径复制到结果集，每条路径长度为 O(n)，共 O(n) 条路径。

空间复杂度：O(n)，递归栈深度为树的高度 h，最坏情况下 h = n；path 列表额外占用 O(h) 空间。

class Solution {

    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        dfs(root, target);
        return res;
    }

    private void dfs(TreeNode node, int remaining) {
        if (node == null) {
            return;
        }
        // 将当前节点加入路径
        path.add(node.val);
        remaining -= node.val;
        // 到达叶子节点且路径和等于目标值，记录当前路径
        if (node.left == null && node.right == null && remaining == 0) {
            res.add(new ArrayList<>(path));
        }
        // 递归遍历左右子树
        dfs(node.left, remaining);
        dfs(node.right, remaining);
        // 回溯，移除当前节点
        path.remove(path.size() - 1);
    }
}

func pathTarget(root *TreeNode, target int) [][]int {
	var res [][]int
	var path []int

	var dfs func(node *TreeNode, remaining int)
	dfs = func(node *TreeNode, remaining int) {
		if node == nil {
			return
		}
		// 将当前节点加入路径
		path = append(path, node.Val)
		remaining -= node.Val
		// 到达叶子节点且路径和等于目标值，记录当前路径
		if node.Left == nil && node.Right == nil && remaining == 0 {
			res = append(res, append([]int{}, path...))
		}
		// 递归遍历左右子树
		dfs(node.Left, remaining)
		dfs(node.Right, remaining)
		// 回溯，移除当前节点
		path = path[:len(path)-1]
	}

	dfs(root, target)
	return res
}

相似题目

题目	难度	考察点
112. 路径总和	简单	DFS / 递归
113. 路径总和 II	中等	DFS / 回溯 / 收集路径
437. 路径总和 III	中等	DFS + 前缀和 / 哈希表
124. 二叉树中的最大路径和	困难	DFS / 后序遍历
129. 求根节点到叶节点数字之和	中等	DFS / 路径求和
257. 二叉树的所有路径	简单	DFS / 回溯 / 路径收集

本文作者: HGNULB

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