leetcode hot100【LeetCode 230. 二叉搜索树中第K小的元素】java实现

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

题目描述

给定一个二叉搜索树的根节点 root，和一个整数 k，请你找出其中第 k 小的节点。

注意：

• 题目保证 k 的有效性。

示例：

给定二叉搜索树：

    5/ \3   7/ \   \
2   4   6

和 k = 2，返回值应该是 3（按升序排列，第二个最小的节点是 3）。

Java 实现代码

/*** 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 {public int kthSmallest(TreeNode root, int k) {// 使用一个列表来存储中序遍历的结果List<Integer> list = new ArrayList<>();inorderTraversal(root, list);// 返回第k小的元素return list.get(k - 1);}private void inorderTraversal(TreeNode node, List<Integer> list) {if (node == null)return;// 遍历左子树inorderTraversal(node.left, list);// 访问当前节点list.add(node.val);// 遍历右子树inorderTraversal(node.right, list);}
}

解题思路

由于二叉搜索树的性质，中序遍历的结果就是升序的。因此，我们可以通过中序遍历来获取所有节点的值，并将它们存储在一个列表中。然后，我们可以直接通过索引来获取第 k 小的元素。

复杂度分析

• 时间复杂度：O(N)，其中 N 是树中节点的数量。因为中序遍历需要访问每一个节点。
• 空间复杂度：O(N)，最坏情况下，我们需要存储所有的节点值。在最坏的情况下，树可能是一条链，此时中序遍历的结果就是所有的节点。

这个方法简单且有效，但需要注意，如果树非常大，可能会消耗较多的内存。对于更优的空间复杂度，可以考虑使用迭代的方式进行中序遍历，这样可以将空间复杂度降低到 O(H)，其中 H 是树的高度。