我正在尝试打印BST中的第k个最小元素。第一种解决方案是使用按顺序遍历。下一个解决方案是通过计算当前节点的左子树的大小来找到该节点的索引。完整算法：
Find size of left subtree:
1.If size = k-1, return current node
2.If size>k return (size-k)th node in right subtree
3.If size<k return kth node in left subtree
这可以使用类似的单独计数功能来实现
public class Solution {
public int kthSmallest(TreeNode root, int k) {
//what happens if root == null
//what happens if k > total size of tree
return kthSmallestNode(root,k).val;
}
public static TreeNode kthSmallestNode(TreeNode root,int k){
if(root==null) return root;
int numberOfNodes = countNodes(root.left);
if(k == numberOfNodes ) return root;
if(k<numberOfNodes ) return kthSmallestNode(root.left,k);
else return kthSmallestNode(root.right,k-numberOfNodes );
}
private static int countNodes(TreeNode node){
if(node == null) return 0;
else return 1+countNodes(node.left)+countNodes(node.right);
}
}
但我看到我们多次计算相同树的大小，所以一种方法是像DP方法一样维护一个数组来存储这些大小。
但我想写一个递归的解决方案。这是我写的代码。
class Node {
int data;
Node left;
Node right;
public Node(int data, Node left, Node right) {
this.left = left;
this.data = data;
this.right = right;
}
}
public class KthInBST
{
public static Node createBST(int headData)
{
Node head = new Node(headData, null, null);
//System.out.println(head.data);
return head;
}
public static void insertIntoBst(Node head, int data)
{
Node newNode = new Node(data, null, null);
while(true) {
if (data > head.data) {
if (head.right == null) {
head.right = newNode;
break;
} else {
head = head.right;
}
} else {
if (head.left == null) {
head.left = newNode;
break;
} else {
head = head.left;
}
}
}
}
public static void main(String[] args)
{
Node head = createBST(5);
insertIntoBst(head, 7);
insertIntoBst(head, 6);
insertIntoBst(head, 2);
insertIntoBst(head, 1);
insertIntoBst(head, 21);
insertIntoBst(head, 11);
insertIntoBst(head, 14);
insertIntoBst(head, 3);
printKthElement(head, 3);
}
public static int printKthElement(Node head, int k)
{
if (head == null) {
return 0;
}
int leftIndex = printKthElement(head.left, k);
int index = leftIndex + 1;
if (index == k) {
System.out.println(head.data);
} else if (k > index) {
k = k - index;
printKthElement(head.right, k);
} else {
printKthElement(head.left, k);
}
return index;
}
}
这是打印正确的答案，但多次打印，我明白了为什么它打印多次，但不知道如何避免。还有，如果我想返回节点而不仅仅是打印，我该怎么做？有人能帮我吗？
目标：
递归查找二进制搜索树中的第k个最小元素，并返回与该元素对应的节点。
观察结果：
小于当前元素的元素数量是左子树的大小，因此我们在class Node中引入了一个新成员，即lsize，它表示当前节点的左子树的尺寸，而不是递归地计算其大小。
解决方案：
在每个节点，我们将左子树的大小与k:的当前值进行比较
- 如果
head.lsize + 1 == k：我们答案中的当前节点 - 如果
head.lsize + 1 > k:左子树中的元素大于k，即最小元素位于左子树中。所以，我们向左走 - 如果
head.lsize + 1 < k：当前元素以及左子树中的所有元素小于我们需要找到的第k个元素。因此，我们转到右子树，但也将k减少左子树+1(当前元素)中的元素数量。通过从k中减去这个，我们确保我们已经考虑了小于k并且根为当前节点的左子树(包括当前节点本身)的元素的数量
代码：
class Node {
int data;
Node left;
Node right;
int lsize;
public Node(int data, Node left, Node right) {
this.left = left;
this.data = data;
this.right = right;
lsize = 0;
}
}
public static void insertIntoBst(Node head, int data) {
Node newNode = new Node(data, null, null);
while (true) {
if (data > head.data) {
if (head.right == null) {
head.right = newNode;
break;
} else {
head = head.right;
}
} else {
head.lsize++; //as we go left, size of left subtree rooted
//at current node will increase, hence the increment.
if (head.left == null) {
head.left = newNode;
break;
} else {
head = head.left;
}
}
}
}
public static Node printKthElement(Node head, int k) {
if (head == null) {
return null;
}
if (head.lsize + 1 == k) return head;
else if (head.lsize + 1 > k) return printKthElement(head.left, k);
return printKthElement(head.right, k - head.lsize - 1);
}
更改：
在class Node中引入了一个新成员lsize
insertIntoBst略有修改printKthElement的主要变化拐角情况：
添加一个检查以确保k在1和树的大小之间，否则将返回一个null节点，从而生成NullPointerException。
到目前为止，这是在我尝试过的测试用例上进行的。欢迎提出任何建议或更正。：)