剑指offer -- 二叉搜索树的第K小的结点

解法

二叉搜索树 的特点是比根节点小的永远在左边，大的永远在右边 (可以看我注释里面话的样例的图) 所以我们可以直接用中序遍历(左根右)得到一个排好序的TreeNode的List。然后直接get(k-1) 就好了(因为list小标从0开始)

/*
 运行时间：17ms 占用内存：9832KB
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }
    5
  3   7
 2 4 6  8
}
*/
import java.util.*;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if (pRoot == null || k == 0 ){
            return null;
        }
        List<TreeNode> list = new ArrayList<>();
        getSortTree(list,pRoot);
        if(list.size()<k){
            return null;
        }
        return list.get(k-1);
    }
    public static void getSortTree(List list , TreeNode root){
        if(root == null){
            return ;
        }
        getSortTree(list,root.left);
        list.add(root);
        getSortTree(list,root.right);
    }


}