`

在二元树中找出和为某一值的所有路径

阅读更多
题目:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。

例如输入整数22和如下二元树

                                          10
                                    /   \
                                   5     12
                                 /   \  
                               4     7 

则打印出两条路径:10, 12和10, 5, 7

先弄清楚是什么遍历:这里给出的路径可以看出来,是先序遍历

class Node{
  public int val;
  public Node left;
  public Node right;
}

public FindRoad(Node node,int num,int sum,List stack){
   sum+=node.val;
   stack.add(node.val);
   
   if(node.left==null&&node.right==null&&sum==num){
         打印
   }

   if(node.left!=null){
      FindRoad(node.left,num,sum,stack);
   }
   if(node.right!=null){
      FindRoad(node.right,num,sum,stack);
   }

   sum -= stack.remove(stack.size()-1);

}

分享到:
评论

相关推荐

    Google微软-华为腾讯-面试笔试数据结构和算法编程题目和部分答案

    这其中包括了二元查找树转换为排序双向链表、设计包含min函数的栈、求子数组的最大和、在二元树中找出和为某一值的所有路径、查找最小的k个元素等题目。这些题目都是常见的数据结构和算法面试题目,旨在考察面试者的...

    matla路径规划城市遍历机器人路径等问题精讲:9 求一元二元函数的最小值和零点.zip

    在MATLAB中,路径规划是解决机器人导航、城市遍历问题的关键技术之一。这个压缩包文件"matla路径规划城市遍历机器人路径等问题精讲:9 求一元二元函数的最小值和零点.zip"显然包含了关于如何利用MATLAB求解一元和...

    面试中经常被问到的80道算法题

    在这道题中,我们需要在一个二元树中找出所有和为某一值的路径。为了实现这一目标,我们需要对二元树进行遍历,并使用合适的算法来计算路径的和。 知识点五: 查找最小的 k 个元素 在这道题中,我们需要从一个数组...

    c语言实现离散的真值表判断、并交差集、判断二元关系、判断欧拉图

    并集操作可以将两个集合的所有元素合并到一个集合中,交集操作找出两个集合共有的元素,而差集则表示在第一个集合中存在的但不在第二个集合中的元素。理解这些操作对于数据结构和算法的设计至关重要。 3. **判断...

    算法面试题总结_嵌入式-常用知识&面试题库_大厂面试真题.doc

    4. 在二元树中找出和为某一值的所有路径:本题目考察了二元树和算法的知识,要求从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径,并打印出和与输入整数相等的所有路径。解决方法是使用递归算法...

    微软公司等数据结构+算法面试100题 第1 100题 全部出炉

    4. 在二元树中找出和为某一值的所有路径: - 该问题要求在二元树中找出从根节点到叶子节点的所有路径,这些路径上的节点值之和等于给定值。 - 需要使用深度优先搜索(DFS)算法,递归遍历二元树的所有节点,并将...

    微软等数据结构+算法面试100题

    在二元树中找出和为某一值的所有路径 此题目要求在给定的二元树中,找到所有节点值之和等于给定整数值的路径。这通常可以通过深度优先搜索(DFS)算法来实现,从根节点开始递归地遍历整个树,同时计算从根节点到...

    算法面试题总结.pdf

    四、在二元树中找出和为某一值的所有路径 这个问题要求输入一个整数和一棵二元树,从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径,打印出和与输入整数相等的所有路径。解答中,我们使用回溯...

    c和c++500强面试题

    5. 在二元树中找出和为某一值的所有路径:这是一个递归遍历二元树并记录路径和的问题。可以通过深度优先搜索(DFS)来实现,在递归过程中累加路径上的节点值,当达到叶子节点且路径和等于目标值时,记录该路径。 **...

    【史上最全】算法面试题集锦.pdf

    4. 在二元树中找出和为某一值的所有路径 知识点:二元树遍历、路径问题、回溯法 要找出二元树中所有和为目标值的路径,可以使用回溯法。从根节点开始,递归遍历每个节点,并记录当前路径的和。当达到叶节点时,判断...

    微软等公司数据结构+算法面试100题

    在二元树中找出和为某一值的所有路径 **题目描述**:给定一个整数target和一棵二元树,找出所有路径上的节点值之和等于target的路径。 **解决方案**:采用深度优先搜索(DFS)策略。从根节点开始递归,每经过一个...

    数据结构C问题

    **五、在二元树中找出和为某一值的所有路径** 在二元树中找出所有和为特定值的路径,通常采用深度优先搜索(DFS)策略。从根节点开始,递归地探索每条可能的路径,同时维护一条路径上的节点值总和。当到达叶子节点...

    数据结构+算法面试100题.pdf

    4. 在二元树中找出和为某一值的所有路径 本题目要求输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。解决这个问题的关键是正确...

    刀疤鸭之数据结构面试题

    5. 二元树中找出和为某一值的所有路径: 这个问题可以通过深度优先搜索(DFS)来解决,需要递归地在树中寻找所有可能的路径,直到找到总和等于目标值的路径。 ***K算法: TopK算法涉及到在一组数中找出前k个最大...

    [珍藏版]微软等数据结构+算法面试100题全部出炉[100题V0.1最终完美版]

    #### 2.2 在二元树中找出和为某一值的所有路径 **题目概述**:给定一个整数值和一棵二元树,找出所有从根节点到叶子节点的路径,使得路径上所有节点值的和等于给定的整数值。 **解题思路**: - 采用深度优先搜索...

    二元关系的闭包运算

    例如,传递闭包可以通过Warshall算法来求解,这是一个简单的迭代过程,用于找出所有可能的传递路径。自反和对称闭包则相对直观,只需要直接添加对应的元素对即可。 至于“可视化”,这通常指的是通过图形界面展示...

    各大公司算法面试题

    在二元树中找出和为某一值的所有路径 - **知识点**: 二元树、深度优先搜索(DFS)。 - **解析**: - 要找出二元树中和为特定值的所有路径,可以使用深度优先搜索(DFS)策略,从根节点开始递归地访问每个节点,并...

Global site tag (gtag.js) - Google Analytics