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?

思路：BST中序遍历得到有序序列以下用的是递归，当然也可以用栈

解法一：看leetcode提交记录

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
         int count=0;
         int result=0;
public:
    int kthSmallest(TreeNode* root, int k) {
        if(root==NULL) return 0;
          kthSmallest(root->left,k);
        if(count<k)
        {
        count++;
        if(count==k)
           result=root->val;         
        }
        if(root->right!=NULL)
          kthSmallest(root->right,k);
          return result;
        
    }
     
};

代码二：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 
12         
13 public:
14     int kthSmallest(TreeNode* root, int k) {
15          int count=0;
16          int result=0;
17          inorderTraversal(root,count,result,k);
18          return result;
19        
20     }
21     void inorderTraversal(TreeNode *node,int &count,int &result,int &k)
22     {
23         if(node==NULL) return;
24         inorderTraversal(node->left,count,result,k);
25         
26         if(count<k) 
27         {count++;
28         if(count==k) 
29             {
30                 result=node->val;
31                 return ;
32             }
33         }
34          inorderTraversal(node->right,count,result,k);
35     }
36     
37    
38     
39 };