题目
230. 二叉搜索树中第 K 小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
提示：
- 树中的节点数为 n 。
- 1 <= k <= n <= 104
- 0 <= Node.val <= 104
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
我的代码（Python）
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
if not root:
return 0
cnt = 0
nodeStack = [root]
while len(nodeStack) > 0:
if nodeStack[-1].left:
nodeStack.append(nodeStack[-1].left)
nodeStack[-2].left = None
else:
currNode = nodeStack[-1]
cnt += 1
if cnt == k:
return currNode.val
nodeStack.pop()
if currNode.right:
nodeStack.append(currNode.right)
return 0点评
最近几天都是树相关的题目，很容易就想到中序遍历。实现起来也不难。但是我的做法不好，因为破坏了树的结构。官方的方法不破坏树结构才是正确的。
题目中的扩展部分，我的想法是，如果要频繁修改和查找，应该是要维护这个树结构，其根结点就是要找的第k个数。但这只适用于k固定的情况。
官方答案里是用树的结点计数方式，记录每个结点下面的子结点的数量，要找第k个时计算位置就可以节省很多步骤。这确实更加通用。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog