首页 > 其他分享 >获取二叉搜索树中节点值的和等于指定输入整数的所有路径

获取二叉搜索树中节点值的和等于指定输入整数的所有路径

时间:2023-10-20 14:32:26浏览次数:44  
标签:node return target 路径 dfs 二叉 树中 节点

二叉搜索树(BST)是一种特殊的二叉树,其每个节点的值都大于其左子树的所有节点的值,并且小于其右子树的所有节点的值。由于这种特性,我们可以在BST中快速查找、插入、删除节点。在BST中,我们可以通过遍历所有路径来找到节点值的和等于指定整数的所有路径。

以下是一个使用Python实现的例子:

python复制代码

 class Node:
 def __init__(self, key):
 self.left = None  
 
 self.right = None  
 self.val = key
 
 def findTarget(root, k):

 def dfs(node, target):

 if node is None:

 return []

 path = []

 if node.val == target:

 return [path]

 if node.val < target:

 path.append(node.val)

 return dfs(node.right, target) + dfs(node.left, target)

 else:

 return dfs(node.left, target) + dfs(node.right, target)
 result = []
 bstSet = set()

 for x in dfs(root, k):
 tempSum = sum(x)

 if tempSum not in bstSet:
 bstSet.add(tempSum)
 result.append(x)
 
 return result

在这个例子中,我们首先定义一个BST节点的类,然后定义一个函数来查找BST中所有节点值的和等于指定整数的路径。我们使用深度优先搜索(DFS)来遍历所有路径。对于每个节点,我们检查它的值是否等于目标值,如果等于目标值,则返回当前路径。如果节点的值小于目标值,则将节点的值添加到路径中,并向右子树递归搜索。如果节点的值大于目标值,则向子树递归搜索。在递归搜索过程中,我们使用一个集合来跟踪已经遍历过的路径的和,以避免重复。最后,我们返回所有满足条件的路径。

获取二叉搜索树中节点值的和等于指定输入整数的所有路径_递归


标签:node,return,target,路径,dfs,二叉,树中,节点
From: https://blog.51cto.com/u_15288375/7950906

相关文章

  • 2023-10-04:用go语言,现有一棵无向、无根的树,树中有 n 个节点,按从 0 到 n - 1 编号 给你
    2023-10-04:用go语言,现有一棵无向、无根的树,树中有n个节点,按从0到n-1编号给你一个整数n和一个长度为n-1的二维整数数组edges,其中edges[i]=[ai,bi]表示树中节点ai和bi之间存在一条边。每个节点都关联一个价格。给你一个整数数组price,其中price[i]是第i......
  • 修改新加节点,重新协调分片速度的配置
    PUT_cluster/settings{"transient":{"cluster.routing.allocation.node_concurrent_recoveries":4,"cluster.routing.allocation.cluster_concurrent_rebalance":4,"cluster.routing......
  • [LC96] 不同的二叉搜索树 注解
    本文基于https://leetcode.cn/problems/unique-binary-search-trees/solutions/550154/96-bu-tong-de-er-cha-sou-suo-shu-dong-ta-vn6x/个人感觉博主部分内容讲得跳跃性较强记录如下正文首先是dp数组的定义,我觉得应该直接说明的是,dp[i]意味着有i个节点的搜索树的数量同......
  • 修改串口节点名称
    需求:3368的老主板更换为3568的新主板,为了app兼容两款主板,要求串口号一致。有个ttyS0的口,需要对应改为ttySWK0跟踪驱动代码:dw8250_probe(drivers\tty\serial\8250\8250_dw.c)-->serial8250_register_8250_port(drivers\tty\serial\8250\8250_core.c)-......
  • 节点安装Java 1.8
    下载jdk-8u361-linux-x64.tar.gzhttps://www.oracle.com/java/technologies/downloads上传jdk-8u361-linux-x64.tar.gz到node1以下命令都是在node1上执行解压tar-zxvfjdk-8u361-linux-x64.tar.gz-C/export/server/配置软连接(快捷方式)ln-s/export/server/jdk1.8......
  • kubeadm 加入work 节点集群时报 http://localhost:10248/healthz处理方法
    现象:[kubelet-check]TheHTTPcallequalto'curl-sSLhttp://localhost:10248/healthz'failedwitherror:Get"http://localhost:10248/healthz":dialtcp127.0.0.1:10248:connect:connectionrefused.[kubelet-check]Itseemslikethekube......
  • Base虚拟机克隆集群节点,并固定IP与免密互通
    克隆Base虚拟机先把Base关机,然后右键-管理-克隆选择完整克隆克隆名字这里叫node1重复步骤,克隆node2/node3为了分类,创建了一个大数据集群文件夹以下命令全是root权限执行配置固定IP#修改主机名hostnamectlset-hostnamenode1#修改IPvim/etc/sysconfig/ne......
  • P5018 [NOIP2018 普及组] 对称二叉树
    先递归判断当前子树是不是对称二叉树,如果是就取\(\max\)然后退出,否则继续递归左儿子的左子树和右儿子的右子树、左儿子的右子树和右儿子的左子树判断。最坏情况是每次都递归到叶子,也就是每层都是\(O(n)\)。但一共只有\(O(\logn)\)层,所以时间复杂度是\(O(n\logn)\)。......
  • Leetcode24. 两两交换链表中的节点
    题目描述给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。示例提交的代码classSolution{ListNodenextNode;publicListNodeswapPairs(ListNodehead){//特殊化处理......
  • 代码随想训练营第四天(Python)| 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点
    两两交换链表中的节点关键点:涉及到头节点变动的都使用虚拟节点。画图找出交换节点指向的顺序和退出循环的条件。1、迭代法classSolution:defswapPairs(self,head:Optional[ListNode])->Optional[ListNode]:dummy_node=ListNode(next=head)cur=......