两种套路解判断二叉树是否是完全二叉树

二叉树节点类

    public static class Node {

        public int value;

        public Node left;

        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

套路1：利用二叉树层序遍历&完全二叉树性质

    
    public static boolean isCBT1(Node head) {
        if (head == null) { //若head为null,则认为是完全二叉树
            return true;
        }
        //定义一个队列用于二叉树的层序遍历
        linkedList queue = new linkedList<>();
        //flag变量的含义: 若遇到有一个结点,只有左子树,没有右子树时,flag修改为true.否则,默认是flag
        boolean flag = false;
        //当前遍历到的节点的左子树
        Node left = null;
        //当前遍历到的节点的右子树
        Node right = null;
        queue.add(head);
        //开始层序遍历
        while (!queue.isEmpty()) {

            head = queue.poll();

            left = head.left; //获取到当前head节点的左子树

            right = head.right; //获取到当前head节点的右子树

            //接着判断是否是否不满足完全二叉树的定义,即上面两个条件有任意一个不符合,即不是完全二叉树
            //(left==null&&right!=null) =>条件1  即某节点左子树为null,右子树不为null,则这棵二叉树百分百不是完全二叉树
            //(flag&&(left!=null||right!=null)) =>条件2 即前面遍历时出现了一个节点,只有左子树,没有右子树且当前节点不是叶子结点,那么这棵二叉树也百分百不是完全二叉树
            if ((left == null && right != null) || (flag && (left != null || right != null))) {
                return false;
            }

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

            if (right != null) {
                queue.add(right);
            }

            //此时的Node节点有2种情况
            //1.有左子树,没有右子树
            //2.既没有左子树,也没有右子树
            if (left == null || right == null) { //若发现当前节点没有左子树或没有右子树,则需要修改flag=true
                flag = true;
            }
        }
        //遍历完成,没有发现不符合完全二叉树定义的,则该二叉树是完全二叉树,return true
        return true;
    }

套路2：利用二叉树后序遍历套路(分治思想)---信息收集

    
    public static class Info {

        //是否是满二叉树
        public boolean isFull;

        //是否是完全二叉树
        public boolean isCBT;

        //高度
        public int height;

        public Info(boolean isFull, boolean isCBT, int height) {
            this.isFull = isFull;
            this.isCBT = isCBT;
            this.height = height;
        }
    }


    
    public static boolean isCBT2(Node head) {
        if (head == null) {
            return true;
        }
        return process(head).isCBT;
    }

    
    public static Info process(Node node) {
        if (node == null) { //若node为null,则认为是完全二叉树,是满二叉树,高度为0
            return new Info(true, true, 0);
        }

        Info leftInfo = process(node.left);

        Info rightInfo = process(node.right);

        //高度取左子树和右子树高度中最大值+1
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;

        //若左子树是满二叉树,右子树时满二叉树,且高度相等,则以当前节点为头的二叉树是满二叉树
        boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;

        boolean isCBT = false;

        if (isFull) { //若当前节点为头结点的二叉树是满二叉树,那一定是完全二叉树  上面条件1
            isCBT = true;
        } else {
            if (leftInfo.isCBT && rightInfo.isCBT) { //当前节点是完全二叉树的前提是左子树和右子树均是完全二叉树

                if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) { //上面的条件3
                    isCBT = true;
                }

                if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) { //上面条件4
                    isCBT = true;
                }

                if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) { //上面条件2
                    isCBT = true;
                }
            }
        }
        //信息收集并向当前节点的父节点汇报
        return new Info(isFull, isCBT, height);
    }

伟子哥的小迷弟的总结：

二叉树后序遍历套路和层序遍历套路在二叉树题目中经常用到，一定要看懂，练熟。Stay hungry stay foolish.