『LeetCode|每日一题』----＞二叉搜索树中第K小的元素

news/2024/4/29 10:16:33/文章来源:https://blog.csdn.net/weixin_51065489/article/details/127262250

1.每日一句

2.作者简介

3.二叉搜索树简介

『LeetCode|每日一题』二叉搜索树中第K小的元素

1.每日一题

4.解题思路

4.1 思路分析

4.2 核心代码

4.3 完整代码

4.4 运行结果

1.每日一句

因为时间永远分岔，通往无数的未来

2.作者简介

🏡个人主页：XiaoXiaoChen-2716

📚学习专栏：力扣专栏

🕒发布日期：2022/10/11

3.二叉搜索树简介

二叉搜索树又叫二叉排序树，顾名思义，就是树中的数据已经做好了排序，排序规则是这样的：如果一个根节点有左子树，那么左子树的节点值肯定小于根节点的值，如果一个根节点有右子树，那么右子树的节点值一定大于根节点的值。同样根节点的左子树右子树同样为二叉排序树

在这里插入图片描述

『LeetCode|每日一题』二叉搜索树中第K小的元素

1.每日一题

原文链接--->点我

4.解题思路

4.1 思路分析

通过上文对二叉搜索树的简要特点了解，于是想到了一个最笨的方法——中序遍历，每找到一个节点则计数器加一

S1：写一个函数用来中序遍历，传参的参数同样是节点和K的值，同时需要定义两个整型变量，这里为了方便我定义的全局变量res和count，count就是计数器；

S2：首先二叉搜索树的左子树的值小一些，所以我们先从左子树开始遍历，也就是把root.left作为第一次遍历的参数，这个节点遍历之后，要把计数器count加一；

S3：左子树的第一个节点遍历完之后，要把计数器count和k作比较，如果相等，说明找到了这个节点，把这个值赋值给res即可，如果不相等，那么此时应该遍历右子树，因为右子树的值比根节点大，即把root.right传参进去，递归调用此函数；

S4：还有一个特殊情况，如果root为空，那么就没有递归调用的必要了，直接返回就可以了

S5：如此循环，直到计数器count的值等于k就说明找到了第k小的节点值

4.2 核心代码

    private void mid_search(TreeNode root , int k){if(root == null) return;mid_search(root.left , k);count++;if(count == k){res = root.val;return;}mid_search(root.right , k);}

4.3 完整代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int res , count = 0;public int kthSmallest(TreeNode root, int k) {mid_search(root , k);return res;}private void mid_search(TreeNode root , int k){if(root == null) return;mid_search(root.left , k);count++;if(count == k){res = root.val;return;}mid_search(root.right , k);}
}