二叉搜索树中第k小的元素

题目描述

给定一个二叉搜索树的节点root,和一个整数k,请你设计一个算法查找其中第k个最小元素(从1开始计数)

输入输出样例

Input: root = [3,1,4,null,2], k = 1
Output: 1

题解

这是一道BST的题目，首先BST的具有以下几个特性：

1. 对于BST的每一个节点node,左子树节点的值都比node的值要小，右子树的值都比node的值大
2. 对于BST的每一个节点node，它的左侧子树与右侧子树都是BST

此外，BST还具有一个极其重要的性质：BST的中序遍历是有序的(升序)

针对这道题目而言，我们使用一下BST中序遍历有序的性质就可以轻松的做出。对于查找第几个元素，我们只需要使用计数，等到条件符合就可以结束函数。具体程序如下所示：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rand = 0;
    int res = 0;
    int kthSmallest(TreeNode* root, int k) {
        inorder(root,k);
        return res;
    }
    void inorder(TreeNode* root,int k) {
        if (root == nullptr) return;
        inorder(root->left,k);
        rand++;
        if (k == rand) {
            res = root->val;
            return;
        }
        inorder(root->right,k);
    }
};