您现在的位置是:首页 > Javascript
当前栏目
二叉树中和为某一值的路径
2023-02-19 12:23:56 时间
思路分析
我们举例来做分析,如下图所示,我们准备了一颗二叉树和一个整数22,通过观察后,我们很容易就能看出它有两条路径的节点值加起来和为22。
- 10、5、7
- 10、12
上述两个路径都是从根节点出发到叶子节点的,也就是说路径总是以根节点为起始点,因此我们首先需要遍历根节点。在树的三种遍历方式中,只有前序遍历是首先访问根节点的。
按照前序遍历的顺序去访问这颗二叉树,在访问节点10之后,就会访问节点5。图中二叉树并没有指向父节点的指针,当访问节点5的时候,我们是不知道前面经过了哪些节点的,此时我们就需要准备一个栈,用来存储访问过的节点。
当到达节点5的时候,路径中包含两个节点:10、5。接下来遍历到节点4,我们把这个节点入栈,这时候已经到达叶节点,但栈中的所有节点之和是19。这个和不等于输入的值22,因此它不符合要求的路径。
最后,我们要遍历的节点是12。在遍历这个节点之前,需要先经过节点5回到节点10。同样的,每次当从子节点回到父节点的时候,我们都需要在路径上删除子节点。最后在节点10到达节点12的时候,路径上的两个节点的值之和也是22,因此这也是一条符合要求的路径。
- 分析到这里,我们就找到了一些规律:
- 当用前序遍历的方式访问到某一节点时,就把该节点添加到路径上,并累加该节点的值
- 如果该节点为叶节点,并且路径中节点值的和刚好等于输入的整数,则当前路径符合要求
- 如果该节点非叶节点,则继续访问它的子节点。从节点路径栈中删除当前节点
递归上述过程,直至二叉树的所有节点访问完毕。
实现代码
形成了清晰的思路之后,接下来我们就可以轻松的写出代码了,如下所示:
- 声明需要的变量:已访问过的路径栈、满足预期的路径数组、当前已访问节点的值总和
- 从root节点开始,用前序遍历访问所有节点,筛选并存储满足预期条件的路径
- 取出根节点的值,将其进行累加
- 累加后,将根节点的值压入路径栈中
- 判断是否访问到了叶节点,如果为叶节点且当前已访问的节点路径总和等于预期条件则将路径栈中的路径放入符合条件的路径数组中
- 当前节点非叶节点,则继续递归访问它的左、右子树
- 左、右子树都访问完成后,则代表当前路径不满足预期条件,将其从路径栈中出栈
测试用例
接下来我们用文章开头的例子来测试下上述代码能否正确执行。
如下所示,成功得计算出了两条路径。
我们将节点12改成20,再来测试下,结果如下所示,只有一条路径符合预期。
示例代码
本文用到的代码完整版请移步:
- TreeOperate.ts
- TreeOperate-test.ts
相关文章
- JDK中内嵌JS引擎介绍及使用
- 49195,npm最后的疯狂?盘点10款最有前途JavaScript构建工具
- 译文:5个增强Node.js应用程序增强功能
- 4个例子,吃透 JavaScript 实现的二叉搜索树 BST
- Vue中使用XML和JSON格式互转插件
- JDK中Jshell简单使用(JDK9版本以上或者JDK9版本)
- shiro中的JSP标签支持
- Java技术点-json转对象,对象转json
- SpringBoot+SpringDataJpa @Query之 JPQL使用书写模板(模糊查询and条件查询)
- Spring Boot中的Freemarker模版引擎引用css和js的正确姿势
- Node.js解压版的环境配置及相关常用命令
- JSP学习笔记(6)—— 自定义MVC框架
- JSP学习笔记(5)——Servlet、监听器、过滤器、MVC模式介绍
- Jsp学习笔记(4)——分页查询
- APIJSON简单使用
- JSP学习笔记(3)——JSTL 标签库
- JSP学习笔记(1)——Jsp指令、动作元素和内置对象
- JavaScript ES6 Promise对象
- Web前端——JavaScript扩展补充
- Web前端——表单提交和Js添加选项