解答
方案一
class Solution {
private List<TreeNode> nodes = new LinkedList<>();
public void inorder(TreeNode node) {
if (node == null) {
return;
}
inorder(node.right);
nodes.add(node);
inorder(node.left);
}
public int kthLargest(TreeNode root, int k) {
inorder(root);
if (k > nodes.size()) {
return 0;
}
return nodes.get(nodes.size() - k).val;
}
}
方案二
class Solution {
private List<TreeNode> nodes = new LinkedList<>();
public void inorder(TreeNode node) {
if (node == null) {
return;
}
inorder(node.right);
nodes.add(node);
inorder(node.left);
}
public int kthLargest(TreeNode root, int k) {
inorder(root);
if (k > nodes.size()) {
return 0;
}
return nodes.get(k - 1).val;
}
}
要点
使用中序遍历,完成树节点各元素的排序,然后按照题目要求提取第K大的元素。
方案一和方案二没有本质的区别。