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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    int cnt = 0;
    TreeNode* res = nullptr;
    void mid_traverse(TreeNode* proot, int k) {
        if (proot == nullptr || cnt > k || k == 0) return;
        mid_traverse(proot->left, k);
        cnt++;
        if (cnt == k) res = proot;
        mid_traverse(proot->right, k);
    }
    int KthNode(TreeNode* proot, int k) {
        mid_traverse(proot, k);
        if (res) return res->val;
        return -1;
    }
};

class Solution {
public:
    vector<int> res;  // 借助数组下标
    int KthNode(TreeNode* pRoot, int k) {
        if (pRoot == nullptr || k == 0) return -1;
        KthNode(pRoot->left, k);
        res.push_back(pRoot->val);
        KthNode(pRoot->right, k);
        return k > res.size() ? -1 : res[k-1];
    }
};