《剑指Offer》二叉搜索树的第k个节点——真没你想象中那么难，一招教你秒杀它~

小咪咪 2024-04-08 12:16 49阅读 0赞

![7d347292eba44350818f9b9c87f25e13.png][]

**此解为了更容易让大家理解，所以优化版本放在了最后**

> 思路：对于二叉搜索树而言，中序遍历，就可以得到升序序列，拿到第k小不是秒杀吗？

public int KthNode (TreeNode root, int k) {
            //对于二叉搜索树而言，中序遍历，就可以由小到大排出val值;
            ArrayList<Integer> array = new ArrayList<>();
            //得到顺序排列
            InitArray(root, array);
            //把不满足条件的排除
            if(root == null || array.size() < k || k == 0){
                return -1;
            }
            return array.get(k - 1);
        }
        //得到顺序排列
        private void InitArray(TreeNode root, ArrayList<Integer> array){
            if(root == null){
                return;
            }
            InitArray(root.left, array);
            array.add(root.val);
            InitArray(root.right, array);
        }

> 优化：去掉了顺序表，减少了递归层次，但方法不变，依旧秒杀~

//记录递归次数
        private int count = 0;
        //记录第k小数字
        private int ret = -1;
        public int KthNode (TreeNode root, int k) {
            fundMin(root, k);
            if(ret != -1){
                return ret;
            }else{
                return -1;
            }
        }
        private void fundMin(TreeNode root, int k){
            if(root == null || count > k){
                return;
            }
            fundMin(root.left, k);
            count++;
            //遇到第k小就修改
            if(count == k){
                ret = root.val;
            }
            fundMin(root.right, k);
        }

--------------------

![3bf383139d1944719464d96a8d6651da.gif][]

[7d347292eba44350818f9b9c87f25e13.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/90a64abc49894f5f90a9d365f378f0b2.png
[3bf383139d1944719464d96a8d6651da.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/bd63313204a240e59de9849a248520f0.gif