剑指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&lt;=0: return None 在二叉搜索树（Binary Search Tree，BST）中，第K大节点是指按照节点值排序后，位于第K位置的节点。二叉搜索树是一种特殊的二叉树，其每个节点的左子树上的所有节点的值都小于该节点的值，而右子树上的所有节点的值都大于该节点的值。因此，对于找到第K大的节点，我们可以利用这种特性进行高效地查找。 这里提供两种不同的Python解题思路： **解题思路一：中序遍历** 中序遍历（Inorder Traversal）是二叉搜索树常用的一种遍历方式，它能按照节点值从小到大的顺序依次访问所有节点。我们可以利用这个特性来找到第K大的节点。具体实现如下： ```python 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] ``` 在这段代码中，我们首先定义了一个辅助函数`inorder`来进行中序遍历，将遍历结果存入`res`列表中。遍历完成后，如果`res`的长度小于K，说明不存在第K大节点；否则返回`res[k-1]`，即第K大节点。 **解题思路二：迭代方法，使用栈辅助** 另一种方法是使用栈辅助，自底向上地遍历二叉搜索树。这种方法从根节点开始，不断地将右子节点压入栈中，直到遇到叶子节点或者右子节点为空。然后出栈并减少K的值，直到K减到0时，当前节点就是第K大的节点。具体实现如下： ```python class Solution: def kthLargest(self, root: TreeNode, k: int) -> TreeNode: 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 ``` 在这个解决方案中，我们使用一个栈`stack`来保存待处理的节点，初始时将根节点及其所有右子节点压入栈中。然后不断出栈并更新K值，直到K为0时，栈顶的节点就是我们要找的第K大节点。 这两种方法都是基于二叉搜索树的特性，通过遍历树结构来找到目标节点。第一种方法使用了递归，适合于节点较少且深度不深的情况；第二种方法使用迭代，避免了递归带来的开销，适用于处理大规模数据。选择哪种方法取决于具体问题的规模和性能要求。