题解 | #二叉树之寻找第k大#

1. 题目考察的知识点

二叉搜索树的性质以及中序遍历的理解

2. 题目解答方法的文字分析

由NB25题我们可以知道，二叉搜索树的中序遍历是递增的，因为我们逆中序遍历是递减的，即先右子树，再遍历中间节点，然后遍历左子树，得到的便是递减序列，遍历到第k个值，便是第k大的值。 为求第 k个节点，需要实现以下 三项工作 ： 递归遍历时计数，统计当前节点的序号； 递归到第 k个节点时，应记录结果 resresres ； 记录结果后，后续的遍历即失去意义，应提前终止（即返回）。

3. 本题解析所用的编程语言

java

4. 完整且正确的编程代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param k int整型 
     * @return int整型
     */
     int ans,k;
    public int kthLargest(TreeNode root, int k) {
        this.k =k;
        dfs(root);
        return ans;
    }
    public void dfs(TreeNode root){
        if(root==null){
            return;
        }
        // 中序倒序遍历，右-》中--》左
        dfs(root.right);
        if(k==0)return;
        if(--k==0) ans = root.val;
        dfs(root.left);
    }
}