剑指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;
}
}