当前位置: 首页 > news >正文

二叉树中和为目标值的路径

LCR 153. 二叉树中和为目标值的路径

LCR 153. 二叉树中和为目标值的路径

参考题解

前言

该题考察二叉树中的回溯,使用先序遍历以及路径记录

先序遍历:根左右

路径记录:通过一个“中间人”(path)来记录当前的路径和,当符合目标条件就赋值给res

递归函数–recur()

1、边界条件

  • root为空的时候,直接返回

2、把root.val加入到path中,同时还要对tar减去root.val,即tar -= root.val

3、当root是叶子节点,而且目标值tar等于 0 的时候,即这一条path是符合题目要求的,将path加入到res当中

  • 注意:这里将path加入到res需要新建一个对象,再加入到res中,否则会有数据冲突,后续path发生改变的时候,res中的path也会有改变,因为该path变量始终都是同一个对象,在堆中的地址是一样的,因为才需要新建一个对象再加入到res

4、递归遍历左,右子树

5、由于已经遍历到了叶子节点,因此需要进行回溯,即path.pop()

public void recur(TreeNode root, int tar) {if(root == null) {return;}path.add(root.val); // 加入当前节点值到 pathtar -= root.val;if(tar == 0 && root.left == null && root.right == null) {res.add(new LinkedList<>(path));}recur(root.left, tar);recur(root.right, tar);path.removeLast();
}

pathTarget函数

执行递归函数recur()

返回res

注意:pathres需要定义为全局变量

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

完整代码展示

class Solution {private final List<List<Integer>> res = new LinkedList<>();private final List<Integer> path = new LinkedList<>();public List<List<Integer>> pathTarget(TreeNode root, int target) {recur(root, target);return res;}public void recur(TreeNode root, int tar) {if(root == null) {return;}path.add(root.val); // 加入当前节点值到 pathtar -= root.val;if(tar == 0 && root.left == null && root.right == null) {res.add(new LinkedList<>(path));}recur(root.left, tar);recur(root.right, tar);path.removeLast();}
}

ps:该题的一些思想和全排列有些相似

http://www.hskmm.com/?act=detail&tid=31241

相关文章:

  • 动态库的调用方式
  • 校招面试官揭秘:我们到底在寻找什么样的技术人才?
  • day011
  • nginx
  • 打造一个比人类更懂 Python 的 AI 编程助手
  • 【黑马python】基础 5.Python 函数:参数 返回值 嵌套
  • linux 命令
  • 一试模拟试题(十七)problem 7 另(数竞相关)
  • PaddleOCR源码安装+centos7.6+python3.10
  • 以后尽量多更新
  • 10/14
  • 算法模版
  • newDay10
  • C#/.NET/.NET Core技术前沿周刊 | 第 57 期(2025年10.1-10.12)
  • Cheap Context and Expensive Context
  • [Mysql]快速执行sql文件
  • Agent之殇
  • 元类编程
  • 1014
  • 10.14日学习笔记
  • python 函数参数的形式以及调用方式
  • SpringBoot开发实用篇(热部署 - 配置高级 - 测试 - 数据层解决方案 ) - a
  • 深入探索Next.js中的SSRF漏洞挖掘
  • 工厂方法+抽象工厂设计模式
  • 2025.10总结 - A
  • 访问者Visitor
  • 迭代器模式Iterator
  • WebStorm的安装与使用
  • WinCC Unified必备设置
  • Lexical Feature engineering