判断一棵满二叉树是否为二叉搜索树

import java.util.*;

// 🍎可以先构建整棵树, 再中序遍历, 判断是否递增
// 🍓不过由于满二叉树, i根 2i+1左 2i+2右, 可以不用构建树, 直接中序遍历
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] sp = in.nextLine().split(",");
        if (sp[0].equals("None")) { // 空树
            System.out.print("True");
            return;
        }
        int[] a = new int[sp.length];
        for (int i = 0; i < sp.length; i++) a[i] = Integer.parseInt(sp[i]);

        List<Integer> list = new ArrayList<>();
        dfs(a, 0, list); // 中序遍历

        for (int i = 0; i < list.size() - 1; i++) {  // 判断递增
            if (list.get(i) >= list.get(i + 1)) {
                System.out.print("False");
                return;
            }
        }
        System.out.print("True");
    }

    // 中序
    private static void dfs(int[] a, int i, List<Integer> list) {
        if (i >= a.length) return;
        dfs(a, 2 * i + 1, list);
        list.add(a[i]);
        dfs(a, 2 * i + 2, list);
    }
}

先构建二叉树，然后判断是否为二叉搜索树

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String[] res = sc.nextLine().split(",");
            if (res[0].equals("None")) {
                System.out.println("True");
                return;
            }

            TreeNode root = getTree(res);
            boolean flag = isBST(root);

            if (flag) {
                System.out.println("True");
            } else {
                System.out.println("False");
            }
        }
    }

    /**
    * 判断是否是二叉搜索树
    */
    static TreeNode prev = null;
    public static boolean isBST(TreeNode root) {
        if (root == null) return true;

        if (!isBST(root.left)) return false;
        if (prev != null && prev.val >= root.val) {
            return false;
        }
        prev = root;

        return isBST(root.right);
    }


    /**
    * 构建二叉树
    */
    public static TreeNode getTree(String[] res) {
        TreeNode root = new TreeNode(Integer.parseInt(res[0])), p = root;
        int idx = 0;
        Deque<TreeNode> queue = new ArrayDeque<>();
        while (p != null) {
            if (2 * idx + 1 < res.length) {
                p.left = new TreeNode(Integer.parseInt(res[2 * idx + 1]));
                queue.offer(p.left);
            }
            if (2 * idx + 2 < res.length) {
                p.right = new TreeNode(Integer.parseInt(res[2 * idx + 2]));
                queue.offer(p.right);
            }
            p = queue.poll();
            idx++;
        }

        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(){}

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

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main{
    //递归思路验证
     public static boolean isBalance(List<Integer>A,int pivot){
	     //如果是叶子节点，必满足二叉搜索树定义   
         if((pivot*2+1)>=A.size())
	            return true;
         //若为二叉搜索树，当前节点必满足大于等于左子树的最大值，小于等于右子树的最小值
	        if(LMaxNode(A,pivot*2+1)<=A.get(pivot)&&A.get(pivot)<=RMinNode(A,pivot*2+2))
	        {
	            return isBalance(A,pivot*2+1)&&isBalance(A,pivot*2+2);
	        }else
	            return false;
	    };
    //返回当前树的最小值
	   public static int LMaxNode(List<Integer> A,int pivot){
           while((pivot*2+2)<A.size()){
               pivot=pivot*2+2;
           }
           return A.get(pivot);
       }
    //返回当前树的最大值
     public static int RMinNode(List<Integer> A,int pivot){
             while((pivot*2+1)<A.size()){
                 pivot=pivot*2+1;
             }
             return A.get(pivot);
             
       }
	    public static void main(String[] args){
            //将输入的String转为int数组，剔除None节点
	        Scanner sc=new Scanner(System.in);
	        String[] s=sc.nextLine().split(",");
	        int i=s.length;
	        List<Integer> A=new ArrayList<Integer>();
	        int j=0;
	        while(i>j){
	        	if (!"None".equals(s[j])) {
	        		A.add(Integer.parseInt(s[j]));
				}
	            j++;
	        }
	        System.out.println(isBalance(A,0)==true?"True":"False");
	    }
}

import java.util.Scanner;
public class Main{
    public static boolean isBST(int[] array){
        //不建树 利用满二叉树的性质直接比较大小  
        //左子树(2*i+1) 右子树(2*i+2)
        for(int i = 0; i < array.length/2; i++){
            //左子树小于根节点 右子树大于根节点
            if(array[i] > array[2*i+1] && array[i] < array[2*i+2]){
                //左子树的右子树小于父节点  右子树的左子树大于父节点
                if(i==0||(i%2==1&&array[2*i+2]<array[i/2])||(i%2==0&&array[2*i+1]>array[i/2-1]))
                   continue;
                else
                    return false;
            }
            else
                return false;
        }
        return true;
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String input = in.nextLine();
        String[] s = input.split(",");
        if("None".equals(s[0])){
            System.out.println("True");
            return;
        }
        int[] array = new int[s.length];
        for(int i = 0; i< array.length; i++){
            array[i] = Integer.valueOf(s[i]);
        }
        if(isBST(array))
            System.out.println("True");
        else
            System.out.println("False");
    }
}

import java.util.*;
public class Main {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while(sc.hasNext()) {
        String str = sc.nextLine();
        System.out.println(solution(str) ? "True" : "False");
    }    
    sc.close();
}
    private static boolean solution(String str) {
        String[] tree = str.split(",");
        
        if(str.equals("None") || tree.length == 1) return true;
        int base = tree.length + 1;
        int totalDepth = 0;
        while(base/2 != 1){
            totalDepth++;
            base /= 2;
        }
        return isValidBST(tree, 0, 0, totalDepth);
    }
 
    private static boolean isValidBST(String[] tree, int index, int depth, int totalDepth) {
        if (index >= tree.length / 2) return true;
                 
        int val = Integer.parseInt(tree[index]);
        int left = 2 * index + 1, right = 2 * index + 2;
        
        if(!isValidBST(tree, left, depth + 1, totalDepth) || !isValidBST(tree, right, depth + 1, totalDepth)){
            return false;
        }else{
        	totalDepth -= depth;
        	depth = 0;
            int start = 2 * index + 1;
            while(depth < totalDepth){
                for(int i = start; i < start + (int)Math.pow(2,depth); i++){
                    if(val <= Integer.parseInt(tree[i])){
                        return false;
                    }
                }
                for(int i = start + (int)Math.pow(2,depth); i < start + (int)Math.pow(2,depth + 1); i++){              	
                    if(val >= Integer.parseInt(tree[i])){
                        return false;
                    }
                }
                depth++;
                start = 2 * start + 1;
            }
        }
        return true;
    }
}