公众号开发是不是网站开发站长工具友链检测
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 是树的高度。