（js）leetcode 230. 二叉搜索树中第K小的元素

╰+哭是因爲堅強的太久メ 2022-11-05 13:51 127阅读 0赞

### 题目： ###

> 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
> 
> 示例 1：
> 
> ![3870cb339a1d9e6cc4021778d28bac32.png][]  
> 输入：root = \[3,1,4,null,2\], k = 1  
> 输出：1
> 
>   
> 示例 2：
> 
> ![65f586f0277f2d50f31dcafdffa6cd23.png][]  
> 输入：root = \[5,3,6,2,4,null,null,1\], k = 3  
> 输出：3

### 思路： ###

> 对二叉搜索树进行中序排序，得到的便是升序排列的结果

### 代码实现： ###

/**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {TreeNode} root
     * @param {number} k
     * @return {number}
     */
    var kthSmallest = function(root, k) {
        let res = inorder(root, []);
        return res[k-1];
    };
    
    var inorder = function(root, arr) {
        if(root == null) return arr;
    
        inorder(root.left, arr);
        arr.push(root.val);
        inorder(root.right, arr);
        return arr;
    }

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70][]

[3870cb339a1d9e6cc4021778d28bac32.png]: /images/20221023/8d543fb68de941cdaee71d0e754fc6bf.png
[65f586f0277f2d50f31dcafdffa6cd23.png]: /images/20221023/99132220a55f4403a678171f70f6b3fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70]: /images/20221023/4fb22295c42e437f96d21c1b4558c347.png