《leetCode》：Kth Smallest Element in a BST

题目

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:

You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Follow up:

What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

思路

由于是二叉搜索树，根据二叉树的特点，我们获取其中序遍历并保存在一个数组中，这个数据就是一个排序好的数组，获取这个数组的第k个元素即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define N  
int * sortArr;
int g_index=;
void inorder(struct TreeNode* root){
    if(root==NULL){
        return ;
    }
    inorder(root->left);
    sortArr[g_index++]=root->val;
    inorder(root->right);
}
int kthSmallest(struct TreeNode* root, int k) {
    if(root==NULL||k<){
        return ;
    }
    sortArr=(int *)malloc(N*sizeof(int));
    if(sortArr==NULL){
        exit(EXIT_FAILURE);
    }
    g_index=;
    inorder(root);
    return sortArr[k-];
}