[编程题] lc [剑指 Offer 54二叉搜索树的第k大节点----或者是求第K小元素]

[编程题] lc：剑指 Offer 54. 二叉搜索树的第k大节点

[编程题] JZ：剑指 Offer 62. 二叉搜索树的第k小节点

<1>题目1 描述:

输入输出

思路

根据二叉搜索树的特点:

• 根据二叉搜索树的特点，中序遍历是从小到大排序，求第k小恰好是第k个节点，我们按照左 根 右 搜索。（搜索过程中判断k值是否达到，退出！）
• 中序遍历是从小到大排序，那么求k大恰好是二叉搜索树的倒序的第K个; 即按照右 根 左的方式访问遍历（搜搜过的过程中不断验证K值是否达到退出）

Java代码（求二叉排序树中的第K小）

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    /*思路：根据二叉搜索树的特点，中序遍历是从小到大排序，求第k小恰好是第k个节点，我们按照左 根 右 搜素
          那么求k大恰好是二叉搜索树的倒序的第K个，即按照右 根 左的方式访问遍历（力扣）
        */
    int k;
    TreeNode node;
    TreeNode KthNode(TreeNode pRoot, int k){
        this.k = k;
        dfs(pRoot);
        return node;
        
    }
    
    public void dfs(TreeNode root){
        //递归的退出条件
        if(root==null){return;}
        //左递归
         dfs(root.left);
        //判断返回第k大个元素
        k--;
        if(k==0){node = root;}
        //右递归
         dfs(root.right);
    }
}

Java代码（求二叉排序树中的第K大）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /*思路：根据二叉搜索树的特点，中序遍历是从小到大排序，那么求k大恰好是二叉搜索树的倒序的第K个;
        即按照右 根 左的方式访问遍历
        */
    int k;    
    int res;
    public int kthLargest(TreeNode root, int k) {
        this.k=k;
        dfs(root);
        return res;
    }

    public void dfs(TreeNode root){
        if(root==null){return;}
        //右递归
        dfs(root.right);
        k--;
        if(k==0){ res = root.val;}
        dfs(root.left);
    }
}