Description

面试题54. 二叉搜索树的第k大节点

难度简单16
给定一棵二叉搜索树，请找出其中第k大的节点。
示例 1:
输入: root = [3,1,4,null,2], k = 1

  1.    3
  2.   / \
  3.  1   4
  4.   \
  5.    2

输出: 4
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3

  1.        5
  2.       / \
  3.      3   6
  4.     / \
  5.    2   4
  6.   /
  7.  1

输出: 4
限制：
1 ≤ k ≤ 二叉搜索树元素个数。
解答
利用二叉搜索树的中序遍历的思想。
中序遍历的思路是，先遍历左子树，打印root节点，再遍历右子树，遍历打印的结果是从小到大排序。

  1. void inOrder(TreeNode node){
  2.    if(node == null)
  3.        return;
  4.    inOrder(node.left);
  5.    System.out.println(node.val);
  6.    inOrder(node.right); 
  7. }

而题目的要求是打印第 k 大的节点，我们可以修改下中序遍历让其从大到小遍历，遍历到第 k 大节点时输出。
改进后的中序遍历。只需要调整遍历的顺序，改为先遍历右子树，打印 root 节点，遍历左子树，此时遍历打印的结果就是从大到小的排序。

  1. void inOrder(TreeNode node){
  2.     if(node == null)
  3.         return;
  4.     inOrder(node.right);
  5.     System.out.println(node.val);
  6.     inOrder(node.left);
  7. }

解答代码：

  1. class Solution {
  2.     int k;
  3.     int result;
  4.     public int kthLargest(TreeNode root, int k) {
  5.         this.k = k;
  6.         inOrder(root);
  7.         return  result;
  8.     }
  10.     // 修改 
  11.     public void inOrder(TreeNode node) {
  12.         if(node == null) 
  13.             return ;
  14.         inOrder(node.right);
  15.         if(k == 0) return;  // 提前结束遍历。
  16.         if(--k == 0)
  17.             result = node.val;
  18.         inOrder(node.left);
  19.     }
  20. }

执行结果：通过
执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗 :39.6 MB, 在所有 Java 提交中击败了100.00%的用户