题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树# JAVA实现

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

    //思想：对给定的二叉树进行中序遍历，若始终保持前一个值比后面一个值小，则其为二叉排序树
    private boolean isBST(TreeNode root){
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode p = root;
        int pre = -32767; //pre为最小值
        while(p != null || !stack.isEmpty()){
            if(p != null){
                stack.addFirst(p);
                p = p.left;
            }
            else{
                p = stack.removeFirst();
                if(pre > p.val){
                    return false;
                }
                else{
                    pre = p.val;
                }
                p = p.right;
            }
        }
        return true;
    }

    //思想：对给定的二叉树进行层序遍历，将所有节点加入队列（包括空结点）。当遇到空结点时，查看其后是否有空结点，若有则不是完全二叉树
    private boolean isCBT(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode p;
        queue.offer(root);
        while(!queue.isEmpty()){
            p = queue.poll();
            if(p != null){
                queue.offer(p.left);
                queue.offer(p.right);
            }
            else{
                while(!queue.isEmpty()){
                    p = queue.poll();
                    if(p != null){
                        return false;
                    }
                }
            }
        }
        return true;
    }
}