判断一棵二叉树是否为搜索二叉树和完全二叉树

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

/**
 * NC60 判断一棵二叉树是否为搜索二叉树和完全二叉树
 * @author d3y1
 */
public class Solution {
    private boolean[] result = new boolean[]{true, true};
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 程序入口
     *
     * @param root TreeNode类 the root
     * @return bool布尔型一维数组
     */
    public boolean[] judgeIt (TreeNode root) {
        return solution1(root);
        // return solution2(root);
    }

    private TreeNode pre = null;
    private boolean reachEnd = false;

    private boolean[] solution1(TreeNode root){
        inorder(root);
        levelorder(root);
        // levelorder1(root);
        return result;
    }

    /**
     * 递归: 中序遍历
     * @param root
     */
    private void inorder(TreeNode root){
        if(root == null){
            return;
        }

        inorder(root.left);

        if(pre != null){
            if(pre.val > root.val){
                result[0] = false;
            }
        }
        pre = new TreeNode(root.val);

        inorder(root.right);
    }

    /**
     * 层序遍历: 队列
     * 完全二叉树在遇到空节点之后剩余的应当全是空节点
     * @param root
     */
    private void levelorder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode node;
        while(queue.peek() != null){
            node = queue.poll();
            queue.offer(node.left);
            queue.offer(node.right);
        }

        // 剩余的应当全是空节点
        while(!queue.isEmpty() && queue.peek()==null){
            queue.poll();
        }

        if(!queue.isEmpty()){
            result[1] = false;
        }
    }

    /**
     * 层序遍历: 队列
     * @param root
     */
    private void levelorder1(TreeNode root){
        if(root == null){
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode node;
        while(!queue.isEmpty()){
            node = queue.poll();
            if(reachEnd){
                if(node.left!=null || node.right!=null){
                    result[1] = false;
                    break;
                }
            }else{
                if(node.left==null && node.right==null){
                    reachEnd = true;
                }else if(node.left==null && node.right!=null){
                    result[1] = false;
                    break;
                }else if(node.left!=null && node.right==null){
                    reachEnd = true;
                    queue.offer(node.left);
                }else{
                    queue.offer(node.left);
                    queue.offer(node.right);
                }
            }
        }
    }

    ////////////////////////////////////////////////////////////////////////////////////////

    private LinkedList<Integer> list = new LinkedList<>();
    private StringBuilder sb = new StringBuilder();

    private boolean[] solution2(TreeNode root){
        if(root == null){
            return result;
        }

        inOrder(root);
        levelOrder(root);
        return result;
    }

    /**
     * 中序遍历
     * @param root
     */
    private void inOrder(TreeNode root){
        if(!result[0]){
            return;
        }
        if(root == null){
            return;
        }

        inOrder(root.left);
        if(list.size() == 0){
            list.offer(root.val);
        }else{
            if(root.val <= list.getLast()){
                result[0] = false;
                return;
            }else{
                list.offer(root.val);
            }
        }
        inOrder(root.right);
    }

    /**
     * 层序遍历
     * @param root
     */
    private void levelOrder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        sb.append(root.val);
        queue.offer(root);

        TreeNode node;
        while(!queue.isEmpty()){
            node = queue.poll();
            if(node.left != null){
                sb.append(node.left.val);
                queue.offer(node.left);
            }else{
                sb.append("#");
            }
            if(node.right != null){
                sb.append(node.right.val);
                queue.offer(node.right);
            }else{
                sb.append("#");
            }
        }

        // #符号后面含有数字
        // String regex = "#[0-9]{1,}";
        String regex = "#\\d+";
        Pattern pattern = Pattern.compile(regex);
        Matcher matcher = pattern.matcher(sb.toString());
        if(matcher.find()){
            result[1] = false;
        }
    }
}

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 root TreeNode类 the root
     * @return bool布尔型一维数组
     */
    public boolean[] judgeIt (TreeNode root) {
        // write code here
        boolean[] result = new boolean[2];
        result[0] = isBST(root);
        result[1] = isComplete(root);
        return result;
    }

    public boolean isComplete(TreeNode root) {
        // Write your solution here
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        boolean flag = false;
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur.left == null) {
                flag = true;
            } else if (flag) {
                return false;
            } else {
                queue.offer(cur.left);
            }

            if (cur.right == null) {
                flag = true;
            } else if (flag) {
                return false;
            } else {
                queue.offer(cur.right);
            }
        }
        return true;
    }

    public boolean isBST(TreeNode root) {
        // Write your solution here
        return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    public boolean isBST(TreeNode root, int min, int max) {
        if (root == null) {
            return true;
        }
        if (root.val <= min || root.val >= max) {
            return false;
        }
        return isBST(root.left, min, root.val) && isBST(root.right, root.val, max);
    }
}

int num=Integer.MIN_VALUE;

public boolean[] judgeIt (TreeNode root) {
    // write code here
    return new boolean[]{isSearch(root) ,isFull(root)};
}


public boolean isSearch(TreeNode root){
    if(root==null){
        return true;
    }
    boolean left = isSearch(root.left);
    if(root.val<num){
        return false;
    }
    num=root.val;
    boolean right = isSearch(root.right);
    return left && right;
}

public boolean isFull(TreeNode root){
    if(root==null){
        return true;
    }
    LinkedList<TreeNode> queue=new LinkedList<>();
    queue.add(root);
    boolean flag=false;
    while(!queue.isEmpty()){
        TreeNode node=queue.poll();
        if(node!=null){
            if(!flag){
                queue.add(node.left);
                queue.add(node.right);
            }else{
                return false;
            }
        }else{
            flag=true; 
        }
    }
    return true;
}

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 root TreeNode类 the root
     * @return bool布尔型一维数组
     */

     //思路就算先判断是否为搜索树，然后判断是否为平衡树
    public boolean[] judgeIt (TreeNode root) {
        // write code here
        boolean arr[]=new boolean[2];
        boolean b1=true;
        TreeNode tmpRoot=root;
        ArrayList<Integer> list=new ArrayList<>();
        mid(tmpRoot,list);
        for(int i=1;i<list.size();i++){
            if(list.get(i)<=list.get(i-1)){
                b1=false;
            }
        }
        arr[0]=b1;
        boolean isEmpty=false;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        int sum=0;
        while(!queue.isEmpty()){
            int size=queue.size();
            sum+=size;
            for(int i=0;i<size;i++){
                if(queue.peek()==null){
                    isEmpty=true;
                    queue.poll();
                    continue;
                }else{
                    TreeNode node=queue.poll();
                    if(node!=null&&isEmpty==true){
                        arr[1]=false;
                        return arr;
                    }
                    queue.add(node.left);
                    queue.add(node.right);
                }
            }
            if(sum==list.size()){
                break;
            }
        }
        arr[1]=true;
        return arr;
    }
    public void mid(TreeNode root,ArrayList<Integer> list){
        if(root==null){
            return;
        }
        mid(root.left,list);
        list.add(root.val);
        mid(root.right,list);
    }
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型一维数组
     */
    List<Integer> mid  = new ArrayList<>();
    public boolean[] judgeIt (TreeNode root) {
        // write code here
        return new boolean[]{isSearchTree(root),isAllTree(root)};
        
    }
    public boolean isSearchTree(TreeNode root){
        if(root==null) return true;
        midPrint(root);
        for(int i = 0; i < this.mid.size()-1; i++){
            if(this.mid.get(i) > this.mid.get(i+1)){
                return false;
            }
        }
        return true;
    }
    public boolean isAllTree(TreeNode root){
        if(root==null) return true;
        Deque<TreeNode> q=  new LinkedList<>();
        q.offer(root);
        boolean left = true;
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if(node==null){
                left = false;
            }else{
                if(left==false){
                    return false;
                }
                q.offer(node.left);
                q.offer(node.right);
            }
        }
        return true;
        
    }
    public void midPrint(TreeNode root){
        if(root==null) return;
        midPrint(root.left);
        mid.add(root.val);
        midPrint(root.right);
    }
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型一维数组
     */
    static int preVal = 0;
    public boolean[] judgeIt (TreeNode root) {
        // write code here
        boolean BST = isBST(root);
        boolean CBT = isCBT(root);
        return new boolean[]{BST,CBT};
    }
//判断是否是搜索二叉树
//原则是中序遍历递增，设置一个静态变量preVal用于判断是否递增
//递归调用，先判断左树是否是搜索二叉树，到达递归边界时返回true
//这时候比较叶子结点的val和preVal的大小，如果不是递增，返回false
//如果递增，preVal = 当前节点的val
//然后向右递归
    public boolean isBST(TreeNode root){
        if(root==null){
            return true;
        }
        boolean leftIsBST = isBST(root.left);
        if(!leftIsBST){
            return false;
        }
        if(root.val<=preVal){
            return false;
        }else{
            preVal = root.val;
        }
        return isBST(root.right);
    }
// 判断一棵树是否是完全二叉树的思路
//1>如果树为空，则直接返回错
//2>如果树不为空：层序遍历二叉树
//2.1>如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；
//2.1>如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
//2.2>如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空，
//且则该节点之后的队列中的结点都为叶子节点，该树才是完全二叉树，否则就不是完全二叉树；
    public boolean isCBT(TreeNode root){
        if(root==null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode cur = root;
        queue.add(cur);
        while(!queue.isEmpty()){
            cur = queue.poll();
            if(cur.left!=null&&cur.right!=null){
                queue.add(cur.left);
                queue.add(cur.right);
            }
            if(cur.left==null&&cur.right!=null){
                return false;
            }
            if((cur.left!=null&&cur.right==null)||(cur.left==null&&cur.right==null)){
                while(!queue.isEmpty()){
                    cur = queue.poll();
                    if(cur.left!=null||cur.right!=null){
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

判断完全二叉树使用的方法是比较节点的个数和最后一个节点的编号，对于完全二叉树来说，这应该是相等的。

判断二叉搜索树有两种方法：递归（min,max)，中序遍历单增。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型一维数组
     */
        static class Node{
        TreeNode node;
        int val;
        public Node(TreeNode node,int val){
            this.node=node;
            this.val=val;
        }
    }
    public boolean[] judgeIt (TreeNode root) {
        // write code here
        boolean b1=df1(root,0,Integer.MAX_VALUE);
        boolean b2=isCompleteTree(root);

        return new boolean[]{b1,b2};
    }
    public boolean df1(TreeNode root,int min,int max){
        if(root==null) return true;

        if(root.val<min||root.val>max) return false;

        return df1(root.left,min,root.val)&&df1(root.right,root.val,max);

    }
    public boolean isCompleteTree(TreeNode root) {
   Deque<Node>deque=new LinkedList<>();
   int res=1;//
   int val=1;//
        //将res和val设置为一样，防止只有一个节点的情况
   if(root==null) return true;
   deque.offer(new Node(root,1));
   while(!deque.isEmpty()){
       Node node=deque.poll();
       if(node.node.left!=null){
                val=node.val*2;
           deque.offer(new Node(node.node.left,val));
           res++;

       }
       if(node.node.right!=null){
           val=node.val*2+1;
           deque.offer(new Node(node.node.right,val));
           res++;
       }
       //

   }
   return res==val;
    }

}

public class Solution {
    boolean res[] = {true,true};
    int val = Integer.MIN_VALUE;
    public boolean[] judgeIt (TreeNode root) {
        // write code here
        dfs(root);
        return res;
    }
    public int[] dfs(TreeNode root){
        if(root == null){
           int k[] = new int[2];
           return k;
        }
         int left[] = dfs(root.left);///获取左子树节点情况
        if(root.val <= val){////中序遍历判断是否符合二叉搜索树
            res[0] = false;
        }
         val = root.val;
        int right[] = dfs(root.right);///获取右子树节点情况
        if((left[0]-right[0]) > 1 || right[1] > left[1]){ ///后续遍历判断树的左右子树高度差是否大于1，以及左子树节点数是否大于右子树
            res[1] = false;///不满足完全二叉树
        }
        int k[] = {Math.max(left[0],right[0]) + 1,left[1] + right[1] + 1};///此节点的高度及节点数
        return k;
    }
}

public class Solution {
    public boolean[] judgeIt (TreeNode root) {
        boolean[] res = new boolean[2];
        res[0] = true; res[1] = true;
        if (root == null) return res;
        //res[0] = search(root, Long.MIN_VALUE, Long.MAX_VALUE);
        ArrayList<Integer> temp = new ArrayList<>();
        inorder(root, temp);
        for (int i = 0; i < temp.size() - 1; i++){
            if (temp.get(i) > temp.get(i + 1)) res[0] = false;
        }
        res[1] = all(root);        
        return res;
    }
    // 直接DFS返回钟中序遍历，再遍历temp判断
    void inorder(TreeNode root, ArrayList<Integer> temp){
        if (root == null) return;
        inorder(root.left, temp);
        temp.add(root.val);
        inorder(root.right, temp);    
    }
    //通过边界条件递归判断左右子树是否符合
//     boolean search(TreeNode root, long left, long right){
//         if (root == null) return true;
//         if (root.val > right || root.val < left) return false;
//         return search(root.left, left, root.val) && search(root.right, root.val, right);
//     } 
    boolean all(TreeNode root){
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean flag = false;
        while(queue.size() != 0){            
            TreeNode newroot = queue.poll();
            TreeNode left = newroot.left;
            TreeNode right = newroot.right;
            if ( (left == null && right != null) || // 无左子树有右子树
                (flag && !(left == null && right == null)) ) //有残缺且非叶节点
                return false;
            if (left != null) queue.add(left);
            if (right != null) queue.add(right); 
            // 存在残缺节点
            if (left == null || right == null) flag = true;
        }
        return true;
    }
}

import java.util.*;
public class Solution {
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型一维数组
     */
    public boolean[] judgeIt (TreeNode root) {
        // write code here
        boolean[] b = new boolean[2];
        b[0] = judgeBST(root);
        b[1] = judgeCBT(root);
        return b;
    }
    
    public boolean judgeCBT(TreeNode head){
        if(head != null){
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(head);
            TreeNode l, r;
            boolean leaf = false;
            while(!queue.isEmpty()){
                head = queue.poll();
                l = head.left;
                r = head.right;
                
                if(
                    (leaf && (l != null || r != null)) //遇到了孩子不双全的节点，那么后续节点必须是叶子
                    || 
                    (l == null && r != null)//有右无左返回false
                )
                    return false;
                
                if(l != null)
                    queue.add(l);
                if(r != null)
                    queue.add(r);
                else
                    leaf = true;
            }
        }
        return true;
    }
    
    public boolean judgeBST(TreeNode head){
        if(head != null){
            Stack<TreeNode> stack = new Stack<>();
            int preValue = Integer.MIN_VALUE;
            while(!stack.isEmpty() || head != null){
                if(head != null){//将左边界压栈
                    stack.push(head);
                    head = head.left;
                }else{
                    head = stack.pop();
                    
                    if(preValue > head.val)
                        return false;
                    else
                        preValue = head.val;
                    
                    head = head.right;
                }
            }
        }
        return true;
    }
}

public class Solution {
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型一维数组
     */
    int temp = Integer.MIN_VALUE;
    boolean flag_search = true;
    public boolean[] judgeIt (TreeNode root) {
        // write code here
        boolean[] res = new boolean[2];
        searchTree(root);
        res[0] = flag_search;
        res[1] = completeTree(root);
        return res;
    }
    
    //判断二叉树是否为完全二叉树
    public boolean completeTree(TreeNode root){
        if(root==null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        //将根节点至第一个不为空的节点，弹出队列->压入左右子节点（包括空节点）
        //如果是完全二叉树，此次循环结束，队列里全为空节点
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node!=null){
                queue.add(node.left);
                queue.add(node.right);
            }else{
                break;
            }
        }
        //判断第一次循环后，队列中是否有不为空的节点，若存在则不满足完全二叉树。
        while(!queue.isEmpty()){
            TreeNode node = queue.peek();
            if(node!=null) return false;
            else queue.poll();
        }
        return true;
    }
    
    //判断二叉树是否为搜索二叉树（中序遍历结果递增）    
    public void searchTree(TreeNode root){
        if(root==null) return;
        searchTree(root.left);
        if(root.val<temp) flag_search=false;
        temp=root.val;        
        searchTree(root.right);
    }
}