Medium

题目描述

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

提示：

  • 树中节点总数在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

解题思路

这道题是经典的二叉树回溯问题，需要找出所有从根节点到叶子节点路径和等于目标值的路径。

解题思路

核心思想：使用深度优先搜索(DFS) + 回溯算法。在遍历过程中维护当前路径和当前路径的节点值总和。

算法步骤：

  1. 使用递归进行深度优先遍历
  2. 维护当前路径path和剩余目标值remainingSum
  3. 将当前节点值加入路径，同时更新剩余目标值
  4. 如果到达叶子节点且剩余目标值为0，说明找到一条有效路径
  5. 递归遍历左右子树
  6. 回溯：递归返回时，需要将当前节点从路径中移除，恢复状态

关键点：

  • 必须到达叶子节点才算一条完整路径
  • 回溯时要恢复路径状态，确保不影响其他分支的搜索
  • 注意深拷贝路径到结果集中

这种解法时间复杂度较优，空间复杂度主要取决于递归栈深度和结果存储。

代码实现

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> result;
        vector<int> path;
        dfs(root, targetSum, path, result);
        return result;
    }
    
private:
    void dfs(TreeNode* node, int remainingSum, vector<int>& path, vector<vector<int>>& result) {
        if (!node) return;
        
        path.push_back(node->val);
        remainingSum -= node->val;
        
        // 如果是叶子节点且路径和等于目标值
        if (!node->left && !node->right && remainingSum == 0) {
            result.push_back(path);
        }
        
        // 递归遍历左右子树
        dfs(node->left, remainingSum, path, result);
        dfs(node->right, remainingSum, path, result);
        
        // 回溯：移除当前节点
        path.pop_back();
    }
};

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        result = []
        path = []
        
        def dfs(node, remaining_sum):
            if not node:
                return
            
            path.append(node.val)
            remaining_sum -= node.val
            
            # 如果是叶子节点且路径和等于目标值
            if not node.left and not node.right and remaining_sum == 0:
                result.append(path[:])  # 深拷贝当前路径
            
            # 递归遍历左右子树
            dfs(node.left, remaining_sum)
            dfs(node.right, remaining_sum)
            
            # 回溯：移除当前节点
            path.pop()
        
        dfs(root, targetSum)
        return result

public class Solution {
    public IList<IList<int>> PathSum(TreeNode root, int targetSum) {
        IList<IList<int>> result = new List<IList<int>>();
        List<int> path = new List<int>();
        Dfs(root, targetSum, path, result);
        return result;
    }
    
    private void Dfs(TreeNode node, int remainingSum, List<int> path, IList<IList<int>> result) {
        if (node == null) return;
        
        path.Add(node.val);
        remainingSum -= node.val;
        
        // 如果是叶子节点且路径和等于目标值
        if (node.left == null && node.right == null && remainingSum == 0) {
            result.Add(new List<int>(path));
        }
        
        // 递归遍历左右子树
        Dfs(node.left, remainingSum, path, result);
        Dfs(node.right, remainingSum, path, result);
        
        // 回溯：移除当前节点
        path.RemoveAt(path.Count - 1);
    }
}

var pathSum = function(root, targetSum) {
    const result = [];
    
    function dfs(node, currentPath, currentSum) {
        if (!node) return;
        
        currentPath.push(node.val);
        currentSum += node.val;
        
        if (!node.left && !node.right && currentSum === targetSum) {
            result.push([...currentPath]);
        }
        
        dfs(node.left, currentPath, currentSum);
        dfs(node.right, currentPath, currentSum);
        
        currentPath.pop();
    }
    
    dfs(root, [], 0);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(N²)，其中 N 是树中节点数。最坏情况下需要遍历所有节点，每次找到路径时需要 O(N) 时间复制路径
空间复杂度O(N)，递归栈深度最大为树的高度，路径数组最大长度也为树的高度

相关题目