[数据结构与算法]检测是否为二叉搜索树

题目描述：

给定一个树状结构（可能不是树），检查它是否是二叉搜索树。如果答案为YES，则输出“YES”及其叶子节点总数；否则，输出“NO”。

输入：

• 第一行：1个数字?n

• 以下n几行：每行包含两个值x和y，表示具有 key 的节点是具有 key 的节点x的父节点y。第一个y是 的左孩子x，第二个y是 的右孩子x。如果y是-1，则没有 的对应子代x。请注意，树中所有节点的键都是不同的且为正的。

输出：

• 如果输入树是二叉搜索树，则输出“YES”及其叶子节点总数；否则，输出“NO”。

代码如下：

import java.util.*;

public class T {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int nums = in.nextInt(),index = 1;
        if (nums <= 0){
            System.out.println("NO");
            return;
        }
        int[] tree = new int[(int) Math.pow(4*nums,2)];
        Map<Integer,Integer> map = new HashMap<>();
        Map<Integer,Integer> count = new HashMap<>();
        Map<Integer,Integer> res = new HashMap<>();
        while (nums > 0){
            int x = in.nextInt();
            int y = in.nextInt();
            index = map.getOrDefault(x,1);
            tree[index] = x;
            map.put(x,index);
            if (count.getOrDefault(x,0) > 2 && res.containsKey(y)){
                System.out.println("NO");
                return;
            }else {
                count.put(x,count.getOrDefault(x,0)+1);
            }
            res.put(y,0);
            if(count.getOrDefault(x,0) == 1){
                tree[index * 2 ] = y;
                map.put(y,index*2);
            }else {
                tree[index * 2+1] = y;
                map.put(y,index*2+1);
            }
            nums--;
        }
        if(isValidBST(tree,1,Long.MIN_VALUE, Long.MAX_VALUE)){
            System.out.println("YES "+countLeaf(tree,1));
        }else {
            System.out.println("NO");
        }
        in.close();
    }



    /**
     * 求二叉树的叶子数
     * @param tree
     * @return
     */
    public static int countLeaf(int[] tree,int index){
        if (tree[index] <= 0){
            return 0;
        }
        if (tree[index*2]<=0 && tree[index*2+1]<=0){
            return 1;
        }
        return countLeaf(tree,index*2) + countLeaf(tree,index*2+1);
    }

    /**
     * 判断二叉树是否为二叉搜索树
     * @param tree
     * @param index
     * @param lower
     * @param upper
     * @return
     */
    public static boolean isValidBST(int[] tree,int index, long lower, long upper) {
        if (tree[index] <= 0) {
            return true;
        }
        if (tree[index] <= lower || tree[index] >= upper) {
            return false;
        }
        return isValidBST(tree,index*2, lower, tree[index]) && isValidBST(tree,index*2+1, tree[index], upper);
    }



}