[LeetCode 230] Kth Smallest Element in a BST

Find the k-th smallest element in a binary search tree. Perform an in-order traversal to generate the sorted sequence, store it in an array, and return the k-th element.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> list;
    void queryTree(TreeNode * node)
    {
        if (NULL == node)
        {
            return;
        }
        if (NULL != node->left)
        {
            queryTree(node->left);
        }
        list.push_back(node->val);
        if (NULL != node->right)
        {
            queryTree(node->right);
        }
    }

    int kthSmallest(TreeNode* root, int k) {
        list.clear();
        queryTree(root);
        return list[k-1];
    }
};