题目描述

给定一个二叉搜索树（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

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

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

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个元素。