二叉搜索树的第K个节点

C++ 中序遍历

简单的

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<TreeNode*> res;
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        midOrderTraversal(pRoot);
        if(k>=1 && res.size()>=k) {
            return res[k-1];
        }
        return nullptr;
    }

    void midOrderTraversal(TreeNode* root){
        if(root==nullptr) return;
        midOrderTraversal(root->left);
        res.emplace_back(root);
        midOrderTraversal(root->right);
    }
};

简单易懂，但是千万不要忘了判断K的大小，唉不然报段错误，醉了。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<TreeNode*> res;
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        midOrderTraversal(pRoot, 0, k);
        if(k>=1 && res.size()>=k) {
            return res[k-1];
        }
        return nullptr;
    }

    void midOrderTraversal(TreeNode* root, int index, int k){
        if(root==nullptr || index==k) return;
        midOrderTraversal(root->left, index, k);
        res.emplace_back(root);
        index++;
        midOrderTraversal(root->right, index, k);
    }
};