剑指 Offer 54. 二叉搜索树的第k大节点
题目描述
原题
给定一棵二叉搜索树,请找出其中第k大的节点。
示例 1:
| 输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
|
示例 2:
| 输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4
|
限制:
1 ≤ k ≤ 二叉搜索树元素个数
题解
| class Solution {
public int kthLargest(TreeNode root, int k) {
//二叉搜索树的中序遍历 是有序的
List<Integer> list = new ArrayList<>();
LinkedList<TreeNode> stack = new LinkedList<>();
while(!stack.isEmpty()||root!=null){
while(root!=null){
stack.push(root);
root = root.left;
}
TreeNode node = stack.pop();
list.add(node.val);
if(node.right!=null){
root = node.right;
}
}
//正序 所以list.size()-k
return list.get(list.size()-k);
}
}
|
最后更新:
January 16, 2021
创建日期:
October 17, 2020