题解 | #二叉搜索树的第k个节点#

题目是：找到一个二叉搜索树的第k个节点，如果想解这道题，我们需要先知道什么是二叉搜索树，具有什么性质？

二叉搜索树（Binary Search Tree）：又称为二叉排序树，它或者是一棵空树，或者是具有下列性质的二叉树：

1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 它的左、右子树也分别为二叉排序树。

二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

从二叉搜索树的性质可以看出，我们如果对树进行中序遍历的话，就可以得到一个有序的顺序，将其存入到一个Java集合ArrayList中即可，然后在判断是否存在第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整型
     */
    ArrayList<TreeNode> result = new ArrayList<>();
    public int KthNode (TreeNode proot, int k) {
        // write code here
        //判断 proot是否为空 ，如果为空直接返回 -1
        if(proot == null){
            return -1;
        }
        //中序遍历二叉搜索树 
        All(proot);
        //如果当前k大于树节点的个数 直接返回-1 要求里没有说k为0的时候返回-1 但是通过测试用例可以看出需要加这一个判断
        if(result.size()<k || k==0){
            return -1;
        }
        else{
            return result.get(k-1).val;
        }
    }
    //树的中序遍历模板 ，建议记住。
    public void All(TreeNode root){
        //root为空 直接返回上一层
        if(root == null){
            return ;
        }
        All(root.left);
        result.add(root);
        All(root.right);
    }
}