给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
= =一看就想到中序遍历
public class Solution {
TreeNode KthNode(TreeNode pRoot, int k)
{
if(pRoot==null||k==0) {
return null;
} ArrayList<TreeNode> list = new ArrayList<>();
list=inOrder(list, pRoot);
//要注意这个地方越界
if(k>list.size()) {
return null;
}
return list.get(k-1);
} public ArrayList<TreeNode> inOrder(ArrayList<TreeNode> list,TreeNode pRoot){
if(pRoot==null) {
return list;
} if(pRoot.left!=null) {
list=inOrder(list, pRoot.left);
}
list.add(pRoot);
if(pRoot.right!=null) {
list=inOrder(list, pRoot.right);
}
return list;
} public static void main(String[] args) {
TreeNode n1 = new TreeNode(8);
TreeNode n2 = new TreeNode(6);
TreeNode n3 = new TreeNode(10);
TreeNode n4 = new TreeNode(5);
TreeNode n5 = new TreeNode(7);
TreeNode n6 = new TreeNode(9);
TreeNode n7 = new TreeNode(11);
n1.left=n2;
n1.right=n3;
n2.left=n4;
n2.right=n5;
n3.left=n6;
n3.right=n7;
new Solution().KthNode(n1, 1);
} }