二叉搜索树的第k大节点

---

题目：

题解：

1、中序遍历（倒序）

• 解题思路：中序遍历倒序，存入list，数量等于k时返回；优化是使用k–，即可。

• 复杂度分析：

  • 时间复杂度 O(N)) ： 当树退化为链表时（全部为右子节点），无论 k 的值大小，递归深度都为 N ，占用 O(N) 时间。
  • 空间复杂度 O(N) ： 当树退化为链表时（全部为右子节点），系统使用 O(N) 大小的栈空间。

• 代码：

  class Solution2 {
      LinkedList<Integer> list = new LinkedList();
      int k;
      public int kthLargest(TreeNode root, int k) {
  
          if (root == null) {
              return -1;
          }
          this.k = k;
          dfs(root);
          if (list.size() != 0) {
              return list.removeLast();
          }
          return -1;
      }
  
  
      private void dfs(TreeNode cur) {
          if (cur == null) {
              return;
          }
          dfs(cur.right);
          int a = list.size();
          if (a == k) {
              return;
          }
          list.add(cur.val);
          dfs(cur.left);
  
  
      }
  }

• 优化：

  class Solution3 {
      int res, k;
      public int kthLargest(TreeNode root, int k) {
          if (root == null) {
              return -1;
          }
          this.k = k;
          dfs(root);
          return res;
      }
      void dfs(TreeNode root) {
          if(root == null) return;
          dfs(root.right);
          // 当k == 0 时，不用再继续遍历了，节省时间和空间
          if(k == 0) return;
          if(--k == 0) res = root.val;
          dfs(root.left);
      }
  }