By Long Luo
Leetcode 230. 二叉搜索树中第K小的元素 题解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| 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 提示: 树中的节点数为 n 。 1 <= k <= n <= 10^4 0 <= Node.val <= 10^4 进阶:如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第$k$小的值,你将如何优化算法?
|
方法一:中序遍历 + 递归
思路与算法:
二叉搜索树具有如下性质:
- 结点的左子树只包含小于当前结点的数。
- 结点的右子树只包含大于当前结点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
二叉树的中序遍历即按照访问左子树——根结点——右子树的方式遍历二叉树;在访问其左子树和右子树时,我们也按照同样的方式遍历;直到遍历完整棵树。
因为二叉搜索树和中序遍历的性质,所以二叉搜索树的中序遍历是按照键增加的顺序进行的。于是,我们可以通过中序遍历找到第k个最小元素。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| public int kthSmallest(TreeNode root, int k) { List<Integer> nums = new ArrayList<>(); inOrder(root, nums); return nums.get(k - 1); }
public void inOrder(TreeNode root, List<Integer> numberList) { if (root == null) { return; }
inOrder(root.left, numberList); numberList.add(root.val); inOrder(root.right, numberList); }
|
复杂度分析:
方法二:中序遍历 + 迭代
思路与算法:
方法一使用的是递归来进行中序遍历,实际上,我们也可以使用迭代方法来进行中序遍历,如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| public int kthSmallest(TreeNode root, int k) { Stack<TreeNode> stack = new Stack<>(); List<Integer> nums = new ArrayList<>(); while (root != null || !stack.empty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); nums.add(root.val); root = root.right; }
return nums.get(k - 1); }
|
实际上,使用迭代方法,我们可以在找到答案后就停止,而不需要遍历整棵树,优化后的代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| public int kthSmallest(TreeNode root, int k) { Stack<TreeNode> stack = new Stack<>(); while (root != null || !stack.empty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); k--; if (k == 0) { break; } root = root.right; }
return root.val; }
|
复杂度分析:
-
时间复杂度:O(H+k),其中H是树的高度。在开始遍历之前,我们需要O(H)到达叶结点。当树是平衡树时,时间复杂度取得最小值O(logN+k);当树是线性树(树中每个结点都只有一个子结点或没有子结点)时,时间复杂度取得最大值O(N+k)。
-
空间复杂度:O(H),栈中最多需要存储H个元素。当树是平衡树时,空间复杂度取得最小值O(logN);当树是线性树时,空间复杂度取得最大值O(N)。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗