题目描述

image.png

解题思路

可以使用倒中序遍历。

注意k不能作为参数，因为先遍历右节点，k会先传给它，而不是先减一。k应该作为全局变量。

  1. class Solution {
  2.     public int kthLargest(TreeNode root, int k) {
  3.         this.k = k;
  4.         traversal(root);
  5.         return res;
  6.     }
  8.     int res = 0;
  9.     int k = 0;
  11.     // 倒中序遍历
  12.     public void traversal(TreeNode root) {
  13.         if (root == null) return;
  14.         traversal(root.right);
  15.         if (k == 0) return;
  16.         if (--k == 0) res = root.val;
  17.         traversal(root.left);
  18.     }
  20. }

也可以找倒序的第k个节点

  1. public int kthLargest(TreeNode root, int k) {
  2.     traversal(root, k);
  3.     return k > list.size() ? 0 : list.get(list.size() - k);
  4. }
  6. List<Integer> list = new ArrayList<>();
  8. public void traversal(TreeNode root, int k) {
  10.     if (root == null) {
  11.         return;
  12.     }
  14.     if (root.left != null) kthLargest(root.left, k);
  15.     list.add(root.val);
  16.     if (root.right != null) kthLargest(root.right, k);
  17. }