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

class Solution {
    //存储排序结果
    List<Integer> list = new ArrayList<>();
    public int kthLargest(TreeNode root, int k) {
        middleTraversal(root);
        return list.get(list.size()-k);
    }

    //中序遍历打表
    void middleTraversal(TreeNode root){
        if(root == null) return;
        middleTraversal(root.left);
        list.add(root.val);
        middleTraversal(root.right);
    }
}

class Solution {
    int res, k;
    public int kthLargest(TreeNode root, int k) {
        //将函数的参数k赋值给全局遍历k
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        // 常规的一个递归出口
        if(root == null) return;
        // 递归右子树
        dfs(root.right);
        // 判断在本节点前是否已经到达
        if(k == 0) return;
        // 到达本节点，首先将k-1，之后判断是否到达，若到达记录当前的值为返回结果
        if(--k == 0) res = root.val;
        // 递归左子树
        dfs(root.left);
    }
}