ChunNote
0%

leetCode-230:Kth Smallest Element in a BST

发表于 分类于

问题描述

给定一个搜索二叉树和一个整数 k，要求找出该二叉树中第 k 小的数。题目链接：**点我**

样例输入输出

输入：[1, 2, 3]， k = 2

输出：2

树的形状

2

/ \

1 3

输入：[1]，k = 1

输出：1

问题解法

利用二叉搜索树中序遍历是一个升序数组的特点，用中序遍历的算法对树进行查找，找到第 k 个数时停止查找。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {    
    private int count = 0;
    
    private int result;
    
    public int kthSmallest(TreeNode root, int k) {
        isFind(root, k);
        return result;
    }

    private boolean isFind(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        
        if (isFind(root.left, k)) {
            return true;
        }
        
        count++;
        if (count == k) {
            result = root.val;
            return true;
        }
        
        return isFind(root.right, k);
    }
}