二叉搜索树中第K小的元素(Kth Smallest Element in a BST)

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1： 图裂了

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2： 图裂了

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

  • 树中的节点数为 n 。
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4

**进阶：**如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int getSize(struct TreeNode* root){
    if (root == NULL) return 0;
    return getSize(root->left)+getSize(root->right)+1;
}

int kthSmallest(struct TreeNode* root, int k){
    int leftSize = getSize(root->left);
    if (k <= leftSize){
        return kthSmallest(root->left, k);
    }
    if (k <= leftSize+1){
        return root->val;
    }
    return kthSmallest(root->right,k-leftSize-1);
}

好爽，这个比较简单，写的很爽，可能因为简单？

int search(struct TreeNode* root, int k, int *size){
    if (root == NULL) {
        *size = 0;
        return 0;
    }
    int leftSize = 0;
    int result = search(root->left, k, &leftSize);

    if (k == leftSize) {
        *size = leftSize;
        return result;
    }

    if (k == leftSize+1){
        *size = leftSize+1;
        return root->val;
    }
    int rightSize;
    result = search(root->right, k-(leftSize+1), &rightSize);
    *size = leftSize +1 + rightSize;
    return result;
}

int kthSmallest(struct TreeNode* root, int k){
    int size;
    return search(root,k,&size);
}

用递归

int search(struct TreeNode* root, int* d){
    if (root == NULL) {
        return 0;
    }
    int result = search(root->left, d);

    if (*d == 0) {
        return result;
    }
    (*d)--;
    if (*d == 0){
        return root->val;
    }
    return search(root->right,d);
}

int kthSmallest(struct TreeNode* root, int k){
    return search(root,&k);
}

太猛了