算法详解：二叉树中和为某一值的路径问题

算法详解：二叉树中和为某一值的路径问题

引用

CSDN

1.

https://m.blog.csdn.net/apple_67445472/article/details/141462183

二叉树中和为某一值的路径

问题描述

给定一棵二叉树和一个整数，要求找出所有从树的根结点开始，到叶结点结束，结点值的和等于给定整数的路径。路径定义为从根节点开始一直到叶子节点所经过的所有节点。

例如，下面的二叉树有两条路径的节点值之和为 22：

路径分别是：

• 10 -> 5 -> 7
• 10 -> 12

解题思路

要解决这个问题，可以使用深度优先搜索（DFS）结合回溯法进行路径的遍历与选择。核心思想是从根节点开始，逐步减去当前节点的值，如果在到达叶子节点时，剩余的值刚好为0，则找到了一个符合条件的路径。以下是详细的实现步骤：

1. 递归遍历树：从根节点开始，递归地遍历左子树和右子树。
2. 回溯法：在递归过程中，记录当前路径，并在递归返回时将路径回溯，即将最后一个节点移除，这样可以在不同的路径中复用同一个路径列表。
3. 判断条件：在每次递归中，检查当前节点是否为叶子节点且路径的节点值之和是否等于目标值，如果是，则将当前路径记录下来。

Java代码实现

import java.util.ArrayList;

class TreeNode {
    int val;  // 当前节点的值
    TreeNode left;  // 左子节点
    TreeNode right;  // 右子节点
    TreeNode(int x) { 
        val = x; 
    }
}

public class Solution {
    private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();  // 用于存储所有符合条件的路径

    /**
     * 主函数，用于查找所有路径
     * @param root 根节点
     * @param target 目标和
     * @return 返回所有路径的列表
     */
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        backtracking(root, target, new ArrayList<>());  // 从根节点开始进行回溯
        return ret;  // 返回结果集
    }

    /**
     * 回溯函数，递归查找路径
     * @param node 当前节点
     * @param target 剩余的目标和
     * @param path 当前路径
     */
    private void backtracking(TreeNode node, int target, ArrayList<Integer> path) {
        if (node == null) {
            return;  // 如果当前节点为空，直接返回
        }
        path.add(node.val);  // 将当前节点值加入路径
        target -= node.val;  // 更新目标值，减去当前节点的值
        // 判断是否达到目标值且当前节点为叶子节点
        if (target == 0 && node.left == null && node.right == null) {
            ret.add(new ArrayList<>(path));  // 如果满足条件，将当前路径加入结果集
        } else {
            // 递归处理左子树
            backtracking(node.left, target, path);
            // 递归处理右子树
            backtracking(node.right, target, path);
        }
        // 回溯，移除路径中的最后一个节点
        path.remove(path.size() - 1);
    }
}

代码解析

• ret：保存所有符合条件的路径，是一个包含多个路径的列表。
• FindPath：主函数，初始化递归过程并返回结果。
• backtracking：核心递归函数。参数node为当前处理的节点，target为剩余需要匹配的值，path保存当前路径。

在每次递归中，首先判断当前节点是否为null，如果是，则直接返回。否则，将节点值加入当前路径并更新目标值。若目标值为0且当前节点为叶子节点，则将当前路径加入结果集中。最后一步是回溯，将当前路径中的最后一个节点移除，继续尝试其他路径。

时间复杂度分析

该算法的时间复杂度主要取决于二叉树的深度和每个节点的访问次数。最坏情况下，需要遍历二叉树的每一条路径，其复杂度为 O(N)，其中 N 是树中节点的数量。

总结

通过本文的讲解，相信大家对如何在二叉树中寻找和为某一特定值的路径有了更加深入的理解。通过深度优先搜索和回溯法，我们可以有效地解决这一问题。Java实现中的递归思路清晰且简洁，适用于面试中的二叉树相关问题。