牛客题霸 [二叉搜索树的第k个结点]C++题解/答案

题目:

给定一棵二叉搜索树,请找出其中的第k小的结点。

题解:

二叉搜索树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值

我们写出二叉搜索树的中序遍历,就是2345678.其实是顺序排列的,那我们要找第k小的值,在中序遍历的过程中找第k个元素
nodeCount是探究root的左子树里有几个节点,因为是顺序排列,如果root>k,就说明k在左子树里面,递归左子树就行。如果root<k,就说明k在右子树里面,递归右子树就行,递归右子树时,第k小就改成第 k - node_count-1小(因为右子树全比左子树和根大)

代码:

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */
class Solution {
   
public:
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
   
        
        if(!pRoot) return nullptr;
        int node_count = nodeCount(pRoot->left);
        if (k <= node_count)
            return KthNode(pRoot->left, k);
        if (k == node_count + 1)
            return pRoot;
        return KthNode(pRoot->right, k - node_count-1);
    }
    int nodeCount(TreeNode* root) {
   
        if (!root)return 0;
        return nodeCount(root->left) + nodeCount(root->right) + 1;
    }
};