剑指 Offer 54.——二叉搜索树的第k大节点

题目链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

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

解题过程

方法一：中序遍历，然后取值

二叉搜索数中序遍历的结果就是一个有序数组，算法也很容易写。这里使用了ArrayList类

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private ArrayList<Integer> res = new ArrayList<>();
    public int kthLargest(TreeNode root, int k) {
        midSearch(root);
        return res.get(res.size() - k);
    }

	// 中序遍历
    private void midSearch(TreeNode root){
        if (root == null) {
            return;
        }

        midSearch(root.left);
        res.add(root.val);
        midSearch(root.right);
    }
}

方法二：在方法一的基础上优化

其实，用不着遍历所有的数，只需要找到第 k 大的数就行。

另外，中序遍历也不一定非要先遍历左子树，这题就先遍历右子树

每次遍历就统计一下已经遍历的最大数的个数，遇到等于k时，就返回值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int count = 0, ans = 0;
    private ArrayList<Integer> res = new ArrayList<>();
    public int kthLargest(TreeNode root, int k) {
        midSearch(root, k);
        return ans;
    }

    private void midSearch(TreeNode root, int k){
        if (root == null) return;

        midSearch(root.right, k);
        if (++count == k){
            ans = root.val;
            return;
        }
        midSearch(root.left, k);
        
    }
}

最后

以上就是务实小鸭子为你收集整理的剑指 Offer 54.——二叉搜索树的第k大节点的全部内容，希望文章能够帮你解决剑指 Offer 54.——二叉搜索树的第k大节点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。