本文实例讲述了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 = noneclass 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 = noneclass 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
