剑指Offer(Python多种思路实现):二叉搜索树的第K大节点
剑指Offer(Python多种思路实现):二叉搜索树的第K大节点
面试54题：
题目：二叉搜索树的第K大节点
题：给定一颗二叉搜索树，请找出其中的第k小的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
解题思路一：中序遍历
class Solution:
# 返回对应节点TreeNode
def KthNode(self, pRoot, k):
# write code here
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]
解题思路二：
def kth_largest(self, root: TreeNode, k: int) -> int:
stack, ans = [], None
while stack or root:
while root:
stack.append(root)
root = root.right
root = stack.pop()
k -= 1
ans = root
root = root.left
if k == 0:
return ans
作者：雾行
