全返利网站建设,中国国际室内设计师网,深圳酒店品牌设计公司,建站哪家好 discuzLeetCode 230. 二叉搜索树中第K小的元素
题目描述
给定一个二叉搜索树的根节点 root#xff0c;和一个整数 k#xff0c;请你找出其中第 k 小的节点。
注意#xff1a;
题目保证 k 的有效性。
示例#xff1a;
给定二叉搜索树#xff1a; 5/ \3 7/ \ \
2 4 …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) {// 使用一个列表来存储中序遍历的结果ListInteger list new ArrayList();inorderTraversal(root, list);// 返回第k小的元素return list.get(k - 1);}private void inorderTraversal(TreeNode node, ListInteger 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 是树的高度。
