题目

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

思路 + 代码

其实就是二叉搜索树的中序遍历翻版。

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
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    private int cnt;
    private TreeNode node;
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(k<1)
            return null;
        cnt = 0;
        inOrder(pRoot, k);
        return node;
    }
    private void inOrder(TreeNode pRoot, int k){
        if(cnt>=k || pRoot==null)
            return;
        inOrder(pRoot.left, k);
        cnt++;
        if(cnt==k){
            node = pRoot;
        }
        inOrder(pRoot.right, k);
    }
}