题目描述

题目：二叉搜索树中的第k小元素

给定一个二叉搜索树（BST），编写一个函数来查找树中第k小的元素。请注意，BST的定义是，对于树中的任意节点，其左子树中的所有节点的值都小于该节点的值，其右子树中的所有节点的值都大于该节点的值。BST的根节点存储的是最小的值。

示例：

给定BST

    5
   / \
  3   6
 / \   \
2   4   7

和 k = 3，函数应该返回树中第3小的元素，即4。

注意：

• 你可以假设BST中不存在重复的值。
• k的值总是有效的，即 1 ≤ k ≤ BST中的节点数。

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 示例代码

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 示例代码

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的中序遍历结果是一个递增序列。