题解 | 二叉搜索树的第k个节点

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    //因为是二叉搜索树，中序遍历既是递增的，按照顺序找到第K个就行；
    int ans = -1;
    int Num = 0;    //Num用于记录当前检测是第几个数了，如果遇到了则更新ans

    int KthNode(TreeNode* proot, int k) {
        if(proot == nullptr)return -1;
        if(k == 0)return -1;

        dp(proot, k);

        return ans;
    }

    void dp( TreeNode* curr, int k ){

        if(curr->left)dp(curr->left, k);

        ++Num;
        if(Num == k){ans = curr->val;return;}  //处理本节点

        if(curr->right)dp(curr->right, k);

        return;
    }
};