给定一个修改后的二叉搜索树，找到第 k 个最小元素

Question

假设在给定的二叉树中如果每个节点包含多个子元素，那么找到树中第 k 个最小元素的最佳方法是什么？

请注意，这不是常规的 BST。每个节点都包含其下的子元素的数量。

Answer 1

find_element(root, k)

    if(root.left.nchildren + 1 == k - 1) 
        return root;

    if(root.left.nchildren + 1 >= k)
        return find_element(root.left, k)             

    else 
        return find_element(root.right, k - (root.left.children + 1))

Answer 2

以InOrder遍历方式遍历BST，并将元素存储到数组中。你的数组是一个排序数组。

Answer 3

这就是我得到的：

find (root, k)
{
leftChildCount = root->left->n
rightChildCount = root->right->n

if (leftChildCount+1 == k)
  Print root node
else if (k< leftChildCount)
  Find(root->left,k)
else
  Find(root->right,k-leftChildCount)
}