剑指offer第六十二题。

题目描述

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

解题思路

二叉搜索树的中序遍历就是其排序好的序列，然后取第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
import java.util.LinkedList;
public class Solution {
    LinkedList<TreeNode> list = new LinkedList<>();
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(k == 0 || pRoot == null){
            return null;
        }
        list = fun(pRoot);
        if(k>list.size()){
            return null;
        }
        return list.get(k-1);
    }
    
    //递归中序遍历
    private LinkedList<TreeNode> fun(TreeNode root){
        if(root != null){
            fun(root.left);
            list.add(root);
            fun(root.right);
        }
        return list;
    }
}