本文实例讲述了python实现查找二叉搜索树第k大的节点功能。分享给大家供大家参考，具体如下：
题目描述
给定一个二叉搜索树，找出其中第k大的节点
就是一个中序遍历的过程，不需要额外的数组，便利到节点之后，k减一就行。
代码1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
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