Leetcode 230.二叉搜索树中第k小的元素
程序员文章站
2022-07-08 15:56:34
...
1、题目
2、解法1(递归法)
1、错误的解法(递归使用的深度遍历DFS,不可能在–k==0处停止,所以以下这种方式不合理)
2、正确的递归
class Solution {
public ArrayList<Integer> inorder(TreeNode t, ArrayList<Integer> arr) {
if (t == null) return arr;
inorder(t.left, arr);
arr.add(t.val);
inorder(t.right, arr);
// arr必须是从底层返回,所以身为管理者
// 必须一层层传递下去
return arr;
}
public int kthSmallest(TreeNode root, int k) {
// 可以由相同的元素赋值
ArrayList<Integer> arr = inorder(root, new ArrayList<Integer>());
return arr.get(k-1);
}
}
时间复杂度为O(N),空间复杂度为O(N)
解法2:使用栈(利用了二叉搜索树的中序遍历就是升序数列)
class Solution {
public int inorder(TreeNode t, int k) {
LinkedList<TreeNode> stk = new LinkedList<>();
while (!stk.isEmpty() || t != null) {
while (t != null) {
stk.add(t);
t = t.left;
}
t = stk.removeLast();
if (--k == 0) return t.val;
t = t.right;
}
return -1;
}
public int kthSmallest(TreeNode root, int k) {
return inorder(root, k);
}
}
== 时间复杂度为O(H+k),如果树是平衡树,所以是O(logN+k), 如果不是平衡树,那就是O(N+k),空间复杂度为O(H+k),如果树是平衡树,所以是O(logN+k), 如果不是,那就是O(N+k)==
3、总结
1、写完代码后,再看两遍,防止出错
上一篇: python实现数据库主从状态监控