塞进裤子ヾ(≧O≦)〃嗷~

0%

剑指offer-54二叉搜索树的第k大节点-python

《剑指offer》python实现系列,全目录

题目描述:

给定一棵二叉搜索树,请找出其中的第k大的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值从小到大顺序第三大结点的值为4。

第一想法:

先获得此二叉搜索树的中序遍历,然后返回第k个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:   
def KthNode(self, pRoot, k):
if not pRoot or k<=0:
return None
res=[]

def inorder(pRoot):
if not pRoot:
return []
inorder(pRoot.left)
res.append(pRoot)
inorder(pRoot.right)
inorder(pRoot)
if len(res)<k:
return None
return res[k-1]

第二想法:

在进行遍历的时候,记录输出的节点数,到k时,return

问题,如何跳出深层递归,使用return返回的是上一层

剑指offer方法:

跟我一样

if help:小手一抖点个广告 or 大手一挥资助一下