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

题目：给定一棵二叉搜索树，请找出其中第k大的节点。

这道题是一道简单题，刚开始写的时候没看到是二叉搜索树，所以当成二叉树来做了，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthLargest(TreeNode root, int k) {
      List<Integer>  list = new ArrayList<Integer>();
     LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
      if(root == null) return 0;
      queue.add(root);
      while(!queue.isEmpty()){
          TreeNode node = queue.poll();
          list.add(node.val);
          if(node.left != null){
              queue.add(node.left);
          }
          if(node.right != null){
              queue.add(node.right);
          }
      }
      Collections.sort(list);
      return list.get(list.size()-k);
    }
}

虽然通过了，但是分数不高，然后重新优化了一下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> list = new ArrayList<Integer>();
    public int kthLargest(TreeNode root, int k) {
        midSort(root);
        return list.get(list.size()-k);
    }
    public void midSort(TreeNode root){
        if(root == null) return;
        midSort(root.left);
        list.add(root.val);
        midSort(root.right);
    }
}

我的思路就是先遍历，然后找出数组第k大的，这题主要考的就是二叉搜索树的中序遍历。

本文地址：https://blog.csdn.net/weixin_40392620/article/details/107332126