剑指 Offer 54. 二叉搜索树的第k大节点

题目描述

原题
给定一棵二叉搜索树,请找出其中第k大的节点。
示例 1:
1
输入: root = [3,1,4,null,2], k = 1
2
3
3
/ \
4
1 4
5
\
6
2
7
输出: 4
Copied!
示例 2:
1
输入: root = [5,3,6,2,4,null,null,1], k = 3
2
5
3
/ \
4
3 6
5
/ \
6
2 4
7
/
8
1
9
输出: 4
Copied!
限制:
1 ≤ k ≤ 二叉搜索树元素个数

题解

1
class Solution {
2
public int kthLargest(TreeNode root, int k) {
3
//二叉搜索树的中序遍历 是有序的
4
List<Integer> list = new ArrayList<>();
5
LinkedList<TreeNode> stack = new LinkedList<>();
6
while(!stack.isEmpty()||root!=null){
7
while(root!=null){
8
stack.push(root);
9
root = root.left;
10
}
11
TreeNode node = stack.pop();
12
list.add(node.val);
13
if(node.right!=null){
14
root = node.right;
15
}
16
}
17
//正序 所以list.size()-k
18
return list.get(list.size()-k);
19
}
20
}
Copied!
最近更新 11mo ago
复制链接