[数据结构与算法]Leetcode-230. 二叉搜索树中第K小的元素

链接

230. 二叉搜索树中第K小的元素

题目

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

示例

示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1

?

示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

说明

• 树中的节点数为?n?。
• 1 <= k <= n <= 104
• 0 <= Node.val <= 104

思路

根据二叉搜索树的性质：?若二叉搜索树的左子树不空，则左子树上所有结点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。

因此，只要对二叉搜索树进行中序遍历，得到的便是排序好的数组。

C++ Code

/**
 * 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 {
    vector<int> res;
public:
    int kthSmallest(TreeNode* root, int k) {
        visit(root);
        return res[k-1];
    }
    void visit(TreeNode* root){
        if(root==nullptr) return;
        visit(root->left);
        res.push_back(root->val);
        visit(root->right);
    }
};

?