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

二叉树中和某一的路径

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

32710

剑指Offer | 二叉树中和某一的路径(一)

二叉树中和某一的路径(一) 1题目描述 给定一个二叉树root和一个 sum ,判断是否有从根节点到叶子节点的节点之和等于 sum 的路径。...1.该题路径定义从树的根结点开始往下一直到叶子结点所经过的结点 2.叶子节点是指没有子节点的节点 3.路径只能从父节点到子节点,不能从子节点到父节点 4.总节点数目n 例如:给出如下的二叉树,sum...=22: 返回true,因为存在一条路径 5 -> 4 -> 11 -> 2 的节点之和 22 2思路 & 解答 前面其实我们有做过这道题,而且需要保存路径,因此需要使用队列,,遍历的节点放进队列中...,到叶子节点之后计算和,然后再回溯到上面一层的时候,队列最后一个元素取出来(这个时候需要将和加回来),放进当前的元素。...,直到叶子节点,如果0,那么说明这条路径符合,只要知道任何一条符合即可返回,不需要遍历所有的路径。

27230
领券