当前位置： 面试刷题>> 二叉搜索树中第 K 小的元素(经典算法150题)
### 题目描述
给定一个二叉搜索树（BST），请编写一个函数来找到树中第K小的元素。注意，BST的定义是：对于树中的任意节点X，其左子树中的所有节点的值都小于X的值，而其右子树中的所有节点的值都大于X的值。
### 示例
假设给定的BST如下：
```
5
/ \
3 6
/ \
2 4
/
1
```
- 如果K = 3，那么应该返回4，因为它是第3小的元素。
- 如果K = 1，那么应该返回1，因为它是第1小的元素。
- 如果K = 4，那么应该返回6，因为它是第4小的元素。
### 解题思路
由于BST的性质，我们可以利用中序遍历（左-根-右）来获取一个递增的元素序列，然后直接返回该序列中的第K个元素即可。
### PHP 代码示例
```php
val = $val;
$this->left = $left;
$this->right = $right;
}
}
function kthSmallest($root, $k) {
$result = [];
inorderTraversal($root, $result);
return $result[$k - 1];
}
function inorderTraversal($node, &$result) {
if ($node == null) return;
inorderTraversal($node->left, $result);
$result[] = $node->val;
inorderTraversal($node->right, $result);
}
// 示例用法
$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->left->left->left = new TreeNode(1);
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):
def inorder(node):
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
return inorder(root)[k-1]
# 示例用法
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.left.left.left = TreeNode(1)
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) {
const result = [];
function inorderTraversal(node) {
if (!node) return;
inorderTraversal(node.left);
result.push(node.val);
inorderTraversal(node.right);
}
inorderTraversal(root);
return result[k - 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.left.left.left = new TreeNode(1);
console.log(kthSmallest(root, 3)); // 输出 4
```
这些示例展示了如何在PHP、Python和JavaScript中解决“二叉搜索树中第K小的元素”这一问题。通过中序遍历BST，我们可以轻松获取一个递增的元素序列，并直接返回第K个元素。