当前位置： 面试刷题>> 二叉搜索树(经典算法150题)
### 题目描述
**题目：二叉搜索树中的第k小元素**
给定一个二叉搜索树（BST），编写一个函数来查找树中第k小的元素。请注意，BST的定义是，对于树中的任意节点，其左子树中的所有节点的值都小于该节点的值，其右子树中的所有节点的值都大于该节点的值。BST的根节点存储的是最小的值。
**示例**：
给定BST
```
5
/ \
3 6
/ \ \
2 4 7
```
和 k = 3，函数应该返回树中第3小的元素，即4。
**注意**：
- 你可以假设BST中不存在重复的值。
- k的值总是有效的，即 1 ≤ k ≤ BST中的节点数。
### PHP 示例代码
```php
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
function kthSmallest($root, $k) {
$stack = new SplStack();
$node = $root;
$count = 0;
while (!empty($stack) || $node !== null) {
while ($node !== null) {
$stack->push($node);
$node = $node->left;
}
$node = $stack->pop();
$count++;
if ($count === $k) {
return $node->val;
}
$node = $node->right;
}
return -1; // 理论上不会执行到这里，因为题目保证k是有效的
}
// 示例用法
$root = new TreeNode(5);
$root->left = new TreeNode(3);
$root->right = new TreeNode(6);
$root->left->left = new TreeNode(2);
$root->left->right = new TreeNode(4);
$root->right->right = new TreeNode(7);
echo kthSmallest($root, 3); // 输出: 4
```
### Python 示例代码
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def kthSmallest(root, k):
stack = []
node = root
count = 0
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
count += 1
if count == k:
return node.val
node = node.right
return -1 # 理论上不会执行到这里
# 示例用法
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.right.right = TreeNode(7)
print(kthSmallest(root, 3)) # 输出: 4
```
### JavaScript 示例代码
```javascript
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function kthSmallest(root, k) {
let stack = [];
let node = root;
let count = 0;
while (stack.length > 0 || node !== null) {
while (node !== null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
count++;
if (count === k) {
return node.val;
}
node = node.right;
}
return -1; // 理论上不会执行到这里
}
// 示例用法
const root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(6);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.right = new TreeNode(7);
console.log(kthSmallest(root, 3)); // 输出: 4
```
在以上三种语言的示例代码中，我们使用了中序遍历（左-根-右）的思想来找到BST中的第k小元素，因为BST的中序遍历结果是一个递增序列。