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

二叉搜索树：中序遍历有序；完全二叉树：节点集中在左侧

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布尔型一维数组
     */
    
    private TreeNode max = null;
    private boolean flag = false;

    public boolean[] judgeIt (TreeNode root) {
        // write code here
        // 判断之后的节点是否有小于已遍历结点的最大值
        // 完全二叉树：出现空的位置之后是否有节点
        // 递归三部曲：返回值boolean，参数：root; 返回值
        // 单层逻辑：存储最大值的max，判断当前是否小于max，false
        // 终结：null，返回true
        boolean[] result = new boolean[2];
        result[0] = binarySearch(root);
        result[1] = binaryPerfect(root);
        System.out.println(result[0]);
        System.out.println(result[1]);
        return result;
    }

    // 判断二叉搜索树 
    private boolean binarySearch(TreeNode root) {

        if (root == null) {
            return true;
        }
        
        boolean left = binarySearch(root.left);
        if (!left) {
            return false;
        }
        if (max != null && max.val > root.val) {
            return false;
        }
        max = root;

        return binarySearch(root.right);
    }

    // 使用广度优先搜索
    // 如果已设置标志位，但仍然出现非空情况，则返回false
    private boolean binaryPerfect(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return true;
        }
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            // 处理特殊情况
            if (flag && (node.left != null || node.right != null)) {
                return false;
            }

            if (node.left == null || node.right == null) {
                flag = true;
            }

            if (node.left == null && node.right != null) {
                return false;
            }

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return true;
    }
}