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

二叉树#

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

示例 1：

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

示例 2：

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

递归的解法

思路：只要知道二叉搜索树进行中序遍历，得到的结果一定是一个「严格递增」的有序序列就很简单了

1
/**
2
 * Definition for a binary tree node.
3
 * type TreeNode struct {
4
 *     Val int
5
 *     Left *TreeNode
6
 *     Right *TreeNode
7
 * }
8
 */
9
func kthSmallest(root *TreeNode, k int) int {
10
    res := []int{}
11

12
    var inorder func(*TreeNode)
13
    inorder = func(node *TreeNode){
14
        if node == nil {
15
            return
16
        }
17

18
        inorder(node.Left)
19

20
        res = append(res, node.Val)
21

22
        inorder(node.Right)
23
    }
24

25
    inorder(root)
26
    return res[k-1]
27
}