分析
- 使用栈实现中序遍历
- 中序遍历按照「左 -> 根 -> 右」的顺序访问节点，因此可以使用显式栈来模拟递归
- 通过遍历左子树进入更小的节点，将节点依次压栈，直到左子树遍历完成
- 计数找到第
k 小的元素
- 每次弹出栈顶节点时，计数器
k 减一，直到 k = 0 时，当前节点即为第 k 小的节点
- 右子树遍历
时间复杂度
时间复杂度 O(h + k)，其中 h 是树的高度，k 是目标元素的位置。我们最多遍历 k 个节点，同时需要沿着树的高度走到叶节点
空间复杂度
空间复杂度：O(h)，栈的最大深度为树的高度
C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution
{
public:
int kthSmallest(TreeNode* root, int k)
{
std::stack<TreeNode*> stk; // 显式栈用于模拟递归
while (root || !stk.empty())
{
// 遍历左子树，将节点压栈
while (root)
{
stk.push(root);
root = root->left;
}
// 处理当前节点
root = stk.top(); // 获取栈顶元素
stk.pop();
if (--k == 0) // 如果 k 减到 0，说明找到第 k 小的节点
return root->val;
// 转向右子树
root = root->right;
}
return 0; // 理论上不会执行到这里，保证函数返回值
}
};
|
