leetcode——面试题54.二叉搜索树的第k大节点

给定一棵二叉搜索树&＃xff0c;请找出其中第k大的节点。

解法一&＃xff1a;使用递归和中序遍历

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val &＃61; x
# self.left &＃61; None
# self.right &＃61; Noneclass Solution:def kthLargest(self, root: TreeNode, k: int) -> int:if not root or k&＃61;&＃61;0:return Nonetarget &＃61; []def kth(node): # 中序遍历得到排序的数组if node.right:kth(node.right)target.append(node.val)if node.left:kth(node.left)kth(root)print(target)return target[k-1]

解法二&＃xff1a;使用循环

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val &＃61; x
# self.left &＃61; None
# self.right &＃61; Noneclass Solution:def kthLargest(self, root: TreeNode, k: int) -> int:if not root or k&＃61;&＃61;0:return Nonelists &＃61; []while k!&＃61;0: # 当k&＃61;&＃61;0时&＃xff0c;直接返回节点对应的值if root: # 如果当前节点不为空&＃xff0c;遍历其右节点lists.append(root)root &＃61; root.rightelse: # 如果当前节点为空&＃xff0c;返回队列中的最后一个节点值root &＃61; lists.pop()if k&＃61;&＃61;1:return root.valelse:k-&＃61;1root &＃61; root.left # 对当前节点的左子树进行循环