首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

二叉树中和某一的路径

前言 有一颗二叉树和一个整数,如何找到二叉树中节点的和输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。...思路分析 我们举例来做分析,如下图所示,我们准备了一颗二叉树和一个整数22,通过观察后,我们很容易就能看出它有两条路径的节点加起来和22。...分析到这里,我们就找到了一些规律: 当用前序遍历的方式访问到某一节点时,就把该节点添加到路径上,并累加该节点的 如果该节点叶节点,并且路径中节点的和刚好等于输入的整数,则当前路径符合要求 如果该节点非叶节点...将其进行累加 累加后,根节点的压入路径栈中 判断是否访问到了叶节点,如果叶节点且当前已访问的节点路径总和等于预期条件则将路径栈中的路径放入符合条件的路径数组中 当前节点非叶节点,则继续递归访问它的左...image-20221106172940751 我们节点12改成20,再来测试下,结果如下所示,只有一条路径符合预期。

31910

剑指offer - 二叉树中和某一的路径 - JavaScript

题目描述:输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点的和输入整数的所有路径。路径定义从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。...题目描述 输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点的和输入整数的所有路径。路径定义从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。...解法 1: 前序遍历(递归) 算法实现思路是: 每次来到新节点,节点放入当前保存的路径 检查节点是否是叶节点: 是:路径放入结果中 不是:继续遍历左子树和右子树 上面整个过程就是一个前序遍历,但在遍历的过程中...整体的处理流程是: 取出栈顶的元祖:节点、剩余路径和、路径 如果当前节点是叶节点,且剩余路径和等于节点的 val,那么路径放入结果中 如果右节点不为空,(右节点,剩余路径和 - 右节点,路径+右节点...剪枝的方法就是如果发现当前的节点的大于 sum,停止递归。

57810
领券