蓝桥与力扣刷题（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小的个元素的结果为-1 public int kthSmallest(TreeNode root, int k) { /** 思路：（深度优先搜索DFS） 1.判断根节点是否为空，是返回0 2.根据平衡二叉树（左子树小于根节点，右子树大于根节点）的性质，从左子树开始查找第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 小的元素时返回该元素的值即可。