Kth Smallest Element in a BST解题报告

Description:

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?

Link:

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

解题方法：

用中序遍历整个树，因为会优先遍历到最小的节点，然后再--k，看在哪个节点上k == 0，则用全局变量记录这个节点。

Time Complexity：

O(N)

完整代码：

int kthSmallest(TreeNode* root, int k) 
    {
        int result = 0;
        bool find = false;
        helper(root, k, result, find);
        return result;
    }
    void helper(TreeNode* root, int &k, int &result, bool &find)
    {
        if(!root || find)
            return;
        helper(root->left, k, result, find);
        if(!--k)
        {
            find = true;
            result = root->val;
        }
        helper(root->right, k, result, find);
    }