蓝桥与力扣刷题（230 二叉搜索树中第k小的元素）

题目：给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：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 count = 0 ;int res = -1 ; //声明未找到第K小的个元素的结果为-1public int kthSmallest(TreeNode root, int k) {/**思路：（深度优先搜索DFS）1.判断根节点是否为空，是返回02.根据平衡二叉树（左子树小于根节点，右子树大于根节点）的性质，从左子树开始查找第K小的个元素*/dfs(root,k);return res;}public void dfs(TreeNode node,int k){if(node == null || res != -1){return ;}//遍历左子树，查找第K小的元素dfs(node.left,k);//继续查找第K小的元素count++;//第k小的元素为根节点时，res为根节点的值if(count == k){res = node.val;return ;}//遍历右子树，查找第K小的元素dfs(node.right,k);}
}

总结：解答这道题需要了解二叉搜索树（平衡二叉树）的性质，根据性质使用递归方法来查找第 k 小的元素。分析第 k 小的元素所在的情况：1.查找不到第 k 小的元素所在（二叉树只有5个节点时，找第7小的元素） 2.第 k 小的元素在左子树  3.第 k 小的元素为根节点  4.第 k 小的元素在右子树 在任一种情况种查找到第 k 小的元素时返回该元素的值即可。