[230] Kth Smallest Element in a BST

啊.......無法靜下心來思考啊啊啊啊啊～～～～（抱頭在地上滾來滾去）

用一個index紀錄,跑到第k個的時候就停止兒～～～～

因為是DFS的關係（吧）所以會從最小值開始return, 因此用index來紀錄可！

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     struct TreeNode *left;

 *     struct TreeNode *right;

 * };

 */

int count = 0;

void find(struct TreeNode* root, int *retVal)

{

    if(root==NULL)

        return;

    find(root->left, retVal);

    count--;

    if (count==0)

    {

        *retVal = root->val;

        return ;

    }

    find(root->right, retVal);

    

}

int kthSmallest(struct TreeNode* root, int k){

    count = k;

    int retV;

    find(root, &retV);

    return retV;

}

用兩個偷吃步來做？！

先宣告一個題目中提到的node max大小的array, 拿來存每個value,

另外再用一個global 的k 來紀錄index, 當做到第k個就可以停了, 不必全部traverse完

（但是不知道global 變數到底會不會被討厭XD）

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     struct TreeNode *left;

 *     struct TreeNode *right;

 * };

 */

int array[10000];

int idx;

int global_k;

void find(struct TreeNode* root)

{

    if(root==NULL)

        return;

    find(root->left);

    array[idx++]=root->val;

    if(idx==global_k)

        return;

    find(root->right);    

}

int kthSmallest(struct TreeNode* root, int k){

    idx=0;

    global_k=k;

    find(root);

    return array[k-1];

}