在最优方式中查找二叉搜索树中第k小的元素

虽然这绝对不是问题的最佳解决方案，但这是另一个潜在的解决方案，我认为有些人可能会觉得很有趣：

/**
 * Treat the bst as a sorted list in descending order and find the element 
 * in position k.
 *
 * Time complexity BigO ( n^2 )
 *
 * 2n + sum( 1 * n/2 + 2 * n/4 + ... ( 2^n-1) * n/n ) = 
 * 2n + sigma a=1 to n ( (2^(a-1)) * n / 2^a ) = 2n + n(n-1)/4
 *
 * @param t The root of the binary search tree.
 * @param k The position of the element to find.
 * @return The value of the element at position k.
 */
public static int kElement2( Node t, int k ) {
    int treeSize = sizeOfTree( t );

    return kElement2( t, k, treeSize, 0 ).intValue();
}

/**
 * Find the value at position k in the bst by doing an in-order traversal 
 * of the tree and mapping the ascending order index to the descending order 
 * index.
 *
 *
 * @param t Root of the bst to search in.
 * @param k Index of the element being searched for.
 * @param treeSize Size of the entire bst.
 * @param count The number of node already visited.
 * @return Either the value of the kth node, or Double.POSITIVE_INFINITY if 
 *         not found in this sub-tree.
 */
private static Double kElement2( Node t, int k, int treeSize, int count ) {
    // Double.POSITIVE_INFINITY is a marker value indicating that the kth 
    // element wasn't found in this sub-tree.
    if ( t == null )
        return Double.POSITIVE_INFINITY;

    Double kea = kElement2( t.getLeftSon(), k, treeSize, count );

    if ( kea != Double.POSITIVE_INFINITY )
        return kea;

    // The index of the current node.
    count += 1 + sizeOfTree( t.getLeftSon() );

    // Given any index from the ascending in order traversal of the bst, 
    // treeSize + 1 - index gives the
    // corresponding index in the descending order list.
    if ( ( treeSize + 1 - count ) == k )
        return (double)t.getNumber();

    return kElement2( t.getRightSon(), k, treeSize, count );
}

这个很好用：status：是保存元素是否被找到的数组。k：是要查找的第k个元素。count：在树遍历期间跟踪经过的节点数。

int kth(struct tree* node, int* status, int k, int count)
{
    if (!node) return count;
    count = kth(node->lft, status, k, count);  
    if( status[1] ) return status[0];
    if (count == k) { 
        status[0] = node->val;
        status[1] = 1;
        return status[0];
    }
    count = kth(node->rgt, status, k, count+1);
    if( status[1] ) return status[0];
    return count;
}

好的，这是我的两分钱意见...

int numBSTnodes(const Node* pNode){
     if(pNode == NULL) return 0;
     return (numBSTnodes(pNode->left)+numBSTnodes(pNode->right)+1);
}


//This function will find Kth smallest element
Node* findKthSmallestBSTelement(Node* root, int k){
     Node* pTrav = root;
     while(k > 0){
         int numNodes = numBSTnodes(pTrav->left);
         if(numNodes >= k){
              pTrav = pTrav->left;
         }
         else{
              //subtract left tree nodes and root count from 'k'
              k -= (numBSTnodes(pTrav->left) + 1);
              if(k == 0) return pTrav;
              pTrav = pTrav->right;
        }

        return NULL;
 }

Node FindSmall(Node root, ref int k)
{
    if (root == null || k < 1)
        return null;

    Node node = FindSmall(root.LeftChild, ref k);
    if (node != null)
        return node;

    if (--k == 0)
        return node ?? root;
    return FindSmall(root.RightChild, ref k);
}

找到最小的节点是O(log n)，然后遍历到第k个节点是O(k)，所以总时间复杂度是O(k + log n)。

最佳方法已经存在。但我想为此添加一个简单的代码

int kthsmallest(treenode *q,int k){
int n = size(q->left) + 1;
if(n==k){
    return q->val;
}
if(n > k){
    return kthsmallest(q->left,k);
}
if(n < k){
    return kthsmallest(q->right,k - n);
}

}

int size(treenode *q){
if(q==NULL){
    return 0;
}
else{
    return ( size(q->left) + size(q->right) + 1 );
}}

以下是步骤：

1.为每个节点添加一个字段，指示其根节点所在树的大小。这支持平均O(logN)时间的操作。

2.为了节省空间，只需要一个字段来指示它所在节点的大小即可。我们不需要保存左子树和右子树的大小。

3.进行中序遍历，直到LeftTree == K, LeftTree = Size(T->Left) + 1。

4.以下是示例代码：

int Size(SearchTree T)
{
    if(T == NULL) return 0;
    return T->Size;
}
Position KthSmallest(SearchTree T, int K)
{
    if(T == NULL) return NULL;

    int LeftTree;
    LeftTree = Size(T->Left) + 1;

    if(LeftTree == K) return T;

    if(LeftTree > K){ 
        T = KthSmallest(T->Left, K); 
    }else if(LeftTree < K){ 
        T = KthSmallest(T->Right, K - LeftTree);
    }   

    return T;
}

5. 同样地，我们也可以得到 KthLargest 函数。

public int kthSmallest(TreeNode root, int k) {
     
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();

    while (true) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      k = k - 1;
      if (k == 0) return root.val;
      root = root.right;
    }

}     

Python解决方案 时间复杂度：O(n) 空间复杂度：O(1)

思路是使用Morris中序遍历

class Solution(object):
def inorderTraversal(self, current , k ):
    while(current is not None):    #This Means we have reached Right Most Node i.e end of LDR traversal

        if(current.left is not None):  #If Left Exists traverse Left First
            pre = current.left   #Goal is to find the node which will be just before the current node i.e predecessor of current node, let's say current is D in LDR goal is to find L here
            while(pre.right is not None and pre.right != current ): #Find predecesor here
                pre = pre.right
            if(pre.right is None):  #In this case predecessor is found , now link this predecessor to current so that there is a path and current is not lost
                pre.right = current
                current = current.left
            else:                   #This means we have traverse all nodes left to current so in LDR traversal of L is done
                k -= 1
                if(k == 0):
                    return current.val
                pre.right = None       #Remove the link tree restored to original here 
                current = current.right
        else:               #In LDR  LD traversal is done move to R 
            k -= 1
            if(k == 0):
                return current.val
            current = current.right

    return 0

def kthSmallest(self, root, k):
    return self.inorderTraversal( root , k  )

这就是我想的，而且它有效。它将在O(log n)中运行。

public static int FindkThSmallestElemet(Node root, int k)
    {
        int count = 0;
        Node current = root;

        while (current != null)
        {
            count++;
            current = current.left;
        }
        current = root;

        while (current != null)
        {
            if (count == k)
                return current.data;
            else
            {
                current = current.left;
                count--;
            }
        }

        return -1;


    } // end of function FindkThSmallestElemet

Node kSmallest(Node root, int k) {
  int i = root.size(); // 2^height - 1, single node is height = 1;
  Node result = root;
  while (i - 1 > k) {
    i = (i-1)/2;  // size of left subtree
    if (k < i) {
      result = result.left;
    } else {
      result = result.right;
      k -= i;
    }  
  }
  return i-1==k ? result: null;
}