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

题目：

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

示例 1:

输入: root = [3,1,4,null,2], k = 13/ \1   4\2
输出: 4

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 35/ \3   6/ \2   4/1
输出: 4

限制：

• 1 ≤ k ≤ 二叉搜索树元素个数

-------------------------------------------------------------------------------------------------------------------------------

分析：

           二叉搜索树的特点就是根左<根<根右，所以我们经过思考可知，通过中序遍历（左中右），得到的是二叉搜索树值的升序。

           因为我们要得到第K大的结点值，所以我们要值的降序排列，那么我们就用逆中序遍历（右中左），根据k值来记录当前是第几个结点。

代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {int count,res;public int kthLargest(TreeNode root, int k) {this.count = k;method(root);return res;}public void method(TreeNode root) {if(root==null) return;if(count == 0) return;method(root.right);count--;if(count==0) {res = root.val;}method(root.left);}
}

因为进入递归之后记录数据k很乱，所以我们定义两个类变量count（用来记录当前是第几个结点）和res（用来存储第K大的值）。

思考：

之前我总是想不通为什么method(root.right);调用后要count-- 表示这个结点已经被遍历。

那method(root.left); 后面为什么不count-- 呢？

后来我想通了，我能提出这个问题说明我没懂递归的真谛。这个count--不是method(root.right);的count--。而是root的count-- 说明root这个结点被遍历到了。

递归整体可以这么理解，你就想先遍历一个结点（不带递归）

    public void method(TreeNode root) {if(root==null) return;if(count == 0) return;count--;if(count==0) {res = root.val;}}

当我把递归删掉后，我的目的就是遍历一个结点。

但是当我有遍历需求后，我想先看右边的，再遍历左边的。那么我就直接上下加个递归。

即：

    public void method(TreeNode root) {if(root==null) return;if(count == 0) return;method(root.right);count--;if(count==0) {res = root.val;}method(root.left);}

你可以将复杂的逻辑改成打印一个结点，那么我想先打印左再中再右。那么就上下加递归函数就可以了。

void method(TreeNode root) {if(root == null) return;method(root.left); //左System.out.println(root.val); //打印method(root.right); //右
}

就是这样。