算法的学习笔记—二叉树中和为某一值的路径

本文主要是介绍算法的学习笔记—二叉树中和为某一值的路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

😀前言
在二叉树中寻找和为某一特定值的路径问题是一个经典的面试题，考察了对二叉树的遍历能力以及递归和回溯算法的理解和应用。本文将详细解析这一问题，并提供一个Java实现。

🏠个人主页：尘觉主页

文章目录

😄二叉树中和为某一值的路径
- 🥰问题描述
- 💖解题思路
- 😀Java代码实现
- - 代码解析
  - 时间复杂度分析
- 😄总结

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

🥰问题描述

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

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

ed77b0e6-38d9-4a34-844f-724f3ffa2c12

路径分别是：

10 -> 5 -> 7
10 -> 12

💖解题思路

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

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

😀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);}
}