Python实现查找二叉搜索树第k大的节点功能示例
作者:hustfc 时间:2023-12-17 04:40:09
本文实例讲述了Python实现查找二叉搜索树第k大的节点功能。分享给大家供大家参考,具体如下:
题目描述
给定一个二叉搜索树,找出其中第k大的节点
就是一个中序遍历的过程,不需要额外的数组,便利到节点之后,k减一就行。
代码1
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.k = 0
def recursionKthNode(self, Root):
result = None
if result == None and Root.left:
result = self.recursionKthNode(Root.left)
if result == None:
if self.k == 1:
return Root
self.k -= 1
if result == None and Root.right:
result = self.recursionKthNode(Root.right)
return result
def KthNode(self, Root, k):
if Root == None:
return None
self.k = k
return self.recursionKthNode(Root)
Root = TreeNode(5)
Root.left = TreeNode(3)
Root.left.left = TreeNode(2)
Root.left.right = TreeNode(4)
Root.right = TreeNode(7)
Root.right.left = TreeNode(6)
Root.right.right = TreeNode(8)
print(Solution().KthNode(Root,3).val)
output : 4
代码2
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.k = 0
def InOrder(self, Root):
ans = None
if Root:
if ans == None and Root.left:
ans = self.InOrder(Root.left) #往左遍历
if ans == None and self.k == 1:
ans = Root #遍历到目标节点
if ans == None and self.k != 1: #没有遍历到目标节点,k--
self.k -= 1
if ans == None and Root.right: #往右遍历
ans = self.InOrder(Root.right)
return ans
def KthNode(self, Root, k):
if Root == None or k <= 0:
return None
self.k = k
return self.InOrder(Root)
希望本文所述对大家Python程序设计有所帮助。
来源:https://blog.csdn.net/weixin_36372879/article/details/84951091
标签:Python,二叉搜索树
0
投稿
猜你喜欢
OpenCV 之按位运算举例解析
2023-04-15 02:07:57
图解Vue 响应式流程及原理
2024-05-09 15:26:23
Python处理键映射值操作详解
2021-03-21 03:14:53
xhtml有哪些块级元素
2009-12-06 11:58:00
Jil,高效的json序列化和反序列化库
2023-07-02 05:30:43
详解go-micro微服务consul配置及注册中心
2024-04-23 09:48:20
详解Js模板引擎(TrimPath)
2024-04-10 13:55:36
javascript 函数调用的对象和方法
2010-07-02 12:25:00
完美解决TensorFlow和Keras大数据量内存溢出的问题
2021-09-23 07:07:33
python同步windows和linux文件
2023-12-11 11:44:35
Python操作sqlite3快速、安全插入数据(防注入)的实例
2022-04-22 16:38:14
Ubuntu 18.04配置mysql以及配置远程连接的步骤
2024-01-14 14:54:39
js 采用delete实现继承示例代码
2023-07-17 09:06:52
Python必知必会之os模块实例详解
2023-06-09 22:31:07
Python cookbook(数据结构与算法)实现查找两个字典相同点的方法
2022-07-20 22:09:46
Django 跨域请求处理的示例代码
2022-05-27 17:08:46
Python工厂函数用法实例分析
2022-07-10 05:30:05
Node.js原理阻塞和EventEmitter及其继承的运用实战
2024-05-05 09:21:33
JavaScript实现的鼠标跟随特效示例【2则实例】
2024-04-17 09:50:27
nginx简单配置多个php服务实例教程
2023-06-11 22:53:30