LeetCode230-二叉搜索树中第K小的元素-数据结构-递归-中序遍历

原题链接

中序遍历的顺序就是从小到大排序了，遍历K个就行了

class Solution {
public:
    vector res;

    int kthSmallest(TreeNode* root, int k) {
        dfs(root);
        return res[k - 1];
    }

    void dfs(TreeNode* root){
        if(!root)   return;
        dfs(root -> left);
        res.push_back(root -> val);
        dfs(root -> right);
    }

};

class Solution {
public:
    int k, ans;

    int kthSmallest(TreeNode* root, int _k) {
        k = _k;
        dfs(root);
        return ans;
    }

    bool dfs(TreeNode* root){
        if(!root)   return false;
        if(dfs(root -> left))   return true;
        if( -- k == 0){
            ans = root -> val;
            return true;
        }
        return dfs(root -> right);
    }

};