题目描述

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

输入输出

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

大致思路

利用二叉搜索树中中序遍历依次增加的特点提取第k小的元素

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    int res, order;
    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return res;
    }

    public void inorder(TreeNode root, int k){
        if(root == null) return;
        inorder(root.left, k);
        order++;
        if(k == order){
            res = root.val;
        }
        inorder(root.right, k);
    }
}