推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

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

/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
public class Solution {
   
    TreeNode KthNode(TreeNode pRoot, int k)
    {
   
        
    }


}

思路： 二叉搜索树的中序遍历就是树结点值的递增排列。

使用递归中序遍历二叉搜索树，然后输出第k个结点。

实现：

/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
public class Solution {
   
    //最终结果
    private TreeNode result;
    //计数器
    private int count = 0;
    // 二叉搜索树的中序遍历就是树结点值的递增排列。
    TreeNode KthNode(TreeNode pRoot, int k)
    {
   
        findK(pRoot, k);
        return result;
    }

    private void findK(TreeNode pRoot, int k){
   
        if (pRoot == null || count > k) {
   
            return;
        }
        findK(pRoot.left, k);
        count++;
        if(count == k) {
   
            result = pRoot;
        }
        findK(pRoot.right, k);
    }

}

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。

这里是猿兄，为你分享程序员的世界。

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！

注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！