【二叉树】Leetcode 230. 二叉搜索树中第K小的元素【中等】

二叉搜索树中第K小的元素

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

示例1：

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

解题思路

二叉搜索树的中序遍历结果是有序的，因此可以通过中序遍历来找到第k个最小元素。

• 1、进行中序遍历二叉搜索树，递归地遍历左子树、当前节点、右子树。
• 2、使用一个全局变量count记录当前已经遍历到的节点个数。
• 3、在每次遍历到一个节点时，count加1，如果count等于k，则返回当前节点的值。
• 4、如果count小于k，则继续递归遍历右子树。

Java实现

public class KthSmallestBST {static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val) {this.val = val;}}private int count;private int result;public int kthSmallest(TreeNode root, int k) {count = 0;result = 0;inorderTraversal(root, k);return result;}private void inorderTraversal(TreeNode root, int k) {if (root == null || count >= k) {return;}// 中序遍历，先访问左子树inorderTraversal(root.left, k);// 访问当前节点count++;if (count == k) {result = root.val;return;}// 再访问右子树inorderTraversal(root.right, k);}public static void main(String[] args) {TreeNode root = new TreeNode(3);root.left = new TreeNode(1);root.right = new TreeNode(4);root.left.right = new TreeNode(2);KthSmallestBST solution = new KthSmallestBST();int k = 2;int result = solution.kthSmallest(root, k);System.out.println("The " + k + "th smallest element is: " + result);}
}

时间空间复杂度

• 时间复杂度：O(n)，其中n是二叉搜索树中的节点数，每个节点都需要访问一次。
• 空间复杂度：O(height)，递归调用栈的深度为树的高度。