# BST中的Kth最小元素

## 例子

tree [] = {5，3，6，2，4，null，null，1}
k = 3

3

tree [] = {3，1，4，null，2}
k = 1

1

## 在BST中找到Kth最小元素的幼稚方法

1. 创建一个整数列表，该列表存储BST的有序遍历。
2. 进行有序遍历
3. 如果根不为null，则对左孩子进行有序遍历。
4. 将当前节点的数据插入列表。
5. 递归地对正确的孩子进行有序遍历。
6. 最后，返回存在于列表中第k个位置的元素。

### JAVA代码

import java.util.ArrayList;

public class KthSmallestInBST {
// Class representing node of BST
static class Node {
int data;
Node left, right;

public Node(int data) {
this.data = data;
left = right = null;
}
}

// Function to do in order traversal of BST and store it in array
private static void inorder(Node root, ArrayList<Integer> traversal) {
if (root != null) {
inorder(root.left, traversal);
inorder(root.right, traversal);
}
}

private static int kthSmallest(Node root, int k) {
ArrayList<Integer> traversal = new ArrayList<>();
// Do inorder traversal and store in an array
inorder(root, traversal);

// Return the kth element of the array
return traversal.get(k - 1);
}

public static void main(String[] args) {
// Example 1
Node root = new Node(5);
root.left = new Node(3);
root.right = new Node(6);
root.left.left = new Node(2);
root.left.right = new Node(4);
root.left.left.left = new Node(1);
int k = 3;

System.out.println(kthSmallest(root, k));

// Example 2
Node root2 = new Node(3);
root2.left = new Node(1);
root2.right = new Node(4);
root2.left.right = new Node(2);
k = 1;

System.out.println(kthSmallest(root2, k));
}
}

### C ++代码

#include <bits/stdc++.h>
using namespace std;

// Class representing node of BST
class Node {
public:
int data;
Node *left;
Node *right;
Node(int d) {
data = d;
left = right = NULL;
}
};

// Function to do in order traversal of BST and store it in array
void inorder(Node *root, vector<int> &traversal) {
if (root != NULL) {
inorder(root->left, traversal);
traversal.push_back(root->data);
inorder(root->right, traversal);
}
}

int kthSmallest(Node *root, int k) {
vector<int> traversal;
// Do inorder traversal and store in an array
inorder(root, traversal);

// Return the kth element of the array
return traversal[k - 1];
}

int main() {
// Example 1
Node *root = new Node(5);
root->left = new Node(3);
root->right = new Node(6);
root->left->left = new Node(2);
root->left->right = new Node(4);
root->left->left->left = new Node(1);
int k = 3;

cout<<kthSmallest(root, k)<<endl;

// Example 2
Node *root2 = new Node(3);
root2->left = new Node(1);
root2->right = new Node(4);
root2->left->right = new Node(2);
k = 1;

cout<<kthSmallest(root2, k)<<endl;

return 0;
}
3
1

## 在BST中找到Kth最小元素的最佳方法

1. 从树的根开始。
2. 如果当前节点的leftCount为（k – 1），这是第k个最小的节点，则返回该节点。
3. 如果当前节点的leftCount小于（k – 1），则在右侧子树中搜索，并将k更新为（k – leftCount – 1）。
4. 否则，如果当前节点的leftCount大于（k – 1），则在左侧子树中搜索。

### JAVA代码

public class KthSmallestInBST {
// class representing Node of augmented BST
static class Node {
int data;
int leftCount;
Node left, right;

public Node(int data) {
this.data = data;
this.leftCount = 0;
left = right = null;
}
}

private static Node insert(Node root, int value) {
// Base Case
if (root == null) {
return new Node(value);
}

// If the new node is to be inserted in the left subtree, increment the leftCount
// of the current node by 1
if (value < root.data) {
root.left = insert(root.left, value);
root.leftCount++;
} else if (value > root.data) {
root.right = insert(root.right, value);
}
return root;
}

private static int kthSmallest(Node root, int k) {
// kth smallest element does not exist
if (root == null) {
return -1;
}

// If lefCount is equals to k - 1, this is the kth smallest element
if (root.leftCount == k - 1) {
return root.data;
} else if (root.leftCount > k - 1) {
// If leftCount is greater than k - 1, search in the left subtree
return kthSmallest(root.left, k);
} else {
// Else search in the right subtree
return kthSmallest(root.right, k - root.leftCount - 1);
}
}

public static void main(String[] args) {
// Example 1
Node root = null;
root = insert(root, 5);
root = insert(root, 3);
root = insert(root, 6);
root = insert(root, 2);
root = insert(root, 4);
root = insert(root, 1);
int k = 3;

System.out.println(kthSmallest(root, k));

// Example 2
Node root2 = null;
root2 = insert(root2, 3);
root2 = insert(root2, 1);
root2 = insert(root2, 4);
root2 = insert(root2, 2);
k = 1;

System.out.println(kthSmallest(root2, k));
}
}

### C ++代码

#include <bits/stdc++.h>
using namespace std;

// class representing Node of augmented BST
class Node {
public:
int data;
int leftCount;
Node *left;
Node *right;
Node(int d) {
data = d;
leftCount = 0;
left = right = NULL;
}
};

Node* insert(Node *root, int value) {
// Base Case
if (root == NULL) {
return new Node(value);
}

// If the new node is to be inserted in the left subtree, increment the
// leftCount of the current node by 1
if (value < root->data) {
root->left = insert(root->left, value);
root->leftCount++;
} else if (value > root->data) {
root->right = insert(root->right, value);
}
return root;
}

int kthSmallest(Node* root, int k) {
// kth smallest element does not exist
if (root == NULL) {
return -1;
}

// If lefCount is equals to k - 1, this is the kth smallest element
if (root->leftCount == k - 1) {
return root->data;
} else if (root->leftCount > k - 1) {
// If leftCount is greater than k - 1, search in the left subtree
return kthSmallest(root->left, k);
} else {
// Else search in the right subtree
return kthSmallest(root->right, k - root->leftCount - 1);
}
}

int main() {
// Example 1
Node *root = NULL;
root = insert(root, 5);
root = insert(root, 3);
root = insert(root, 6);
root = insert(root, 2);
root = insert(root, 4);
root = insert(root, 1);
int k = 3;

cout<<kthSmallest(root, k)<<endl;

// Example 2
Node *root2 = NULL;
root2 = insert(root2, 3);
root2 = insert(root2, 1);
root2 = insert(root2, 4);
root2 = insert(root2, 2);
k = 1;

cout<<kthSmallest(root2, k)<<endl;

return 0;
}
3
1