剑指offer10 JZ54 二叉搜索树的第k个节点

思路

根据二叉搜索树的性质，左子树的元素都小于根节点，右子树的元素都大于根节点。因此它的中序遍历（左中右）序列正好是由小到大的次序，因此我们可以尝试递归中序遍历，也就是从最小的一个节点开始，找到k个就是我们要找的目标。

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 proot TreeNode类 
     * @param k int整型 
     * @return int整型
     */
    
    //利用二叉树的性质  左子树比根节点小 右子树比根节点大 
    //记录下访问的次数 就能找出第k小的值
    TreeNode res=null;
    int count=0;//记录中序遍历的访问个数
    public int KthNode (TreeNode proot, int k) {
        // write code here
        midOrder(proot,k);
        if(res==null){
            return -1;
        }
        else{
          return  res.val;
        }
    }
    public void midOrder(TreeNode root,int k){
        if(root==null || count>k){
            return; //终止遍历
        }
        midOrder(root.left,k);// 左子树
        count++; //记录访问节点次数
        if(count==k){
            res=root; //记录下
        }
        midOrder(root.right,k);
        
    }
}