目录
题目概述(简单难度)
题目链接:
思路与代码
思路展现
思路建议大家还是看K神的解答即可:
点我进入解答
代码示例
class Solution {
int res,k;
//注意kthLargest方法要放在dfs方法前,因为涉及到k的赋值
public int kthLargest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}
public void dfs(TreeNode root) {
if(root == null) {
return;
}
dfs(root.right);
if(k == 0) {
return;
}
if(--k == 0) {
res = root.val;
}
dfs(root.left);
}
}
时间复杂度 O(N) : 当树退化为链表时(全部为右子节点),无论 k 的值大小,递归深度都为 N ,占用 O(N)时间。
空间复杂度 O(N): 当树退化为链表时(全部为右子节点),系统使用 O(N) 大小的栈空间。