06、二叉树的递归套路-完全二叉树

题目：

给定一棵二叉树的头节点head，判断这棵树是不是完全二叉树

1、解决方案1

1.1、思路：

 1.2、代码：

public static class Node {
    public int value;
    public Node left;
    public Node right;

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

//方案1：利用宽度优先遍历判断该树是否为完全二叉树
public static boolean isCBT1(Node head) {
    if (head == null) {
        return true;
    }
    LinkedList<Node> queue = new LinkedList<>();
    // 是否遇到过左右两个孩子不双全的节点
    boolean leaf = false;
    Node l = null;
    Node r = null;
    queue.add(head);
    while (!queue.isEmpty()) {
        head = queue.poll();
        l = head.left;
        r = head.right;
        if (
            // 如果遇到了不双全的节点之后，又发现当前节点不是叶节点
                (leaf && !(l == null && r == null))
                        ||
                        //任何节点，如果有右无左，那么一定不是完全二叉树
                        (l == null && r != null)) {
            return false;
        }
        if (l != null) {
            queue.add(l);
        }
        if (r != null) {
            queue.add(r);
        }
        // 说明遇到了叶子节点
        if (l == null || r == null) {
            leaf = true;
        }
    }
    return true;
}
           

 2、解决方案2

2.1、思路：

 2.2、代码：

//方案二：
public static boolean isCBT2(Node head) {
    if (head == null) {
        return true;
    }
    return process(head).isCBT;
}

public static class Info {
    //以该节点为头的子树是否为满二叉树
    public boolean isFull;
    //以该节点为头的子树是否为完全二叉树
    public boolean isCBT;
    public int height;

    public Info(boolean full, boolean cbt, int h) {
        isFull = full;
        isCBT = cbt;
        height = h;
    }
}

public static Info process(Node head) {
    if (head == null) {
        return new Info(true, true, 0);
    }
    Info leftInfo = process(head.left);
    Info rightInfo = process(head.right);
    int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    //左子树为满，右子树也为满，并且左右高度一样，那么以head为头的子树也一定是满的
    boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
    boolean isCBT = false;
    if (isFull) {
        //如果是满二叉树，那么一定是完全二叉树
        isCBT = true;
    } else {
        //左树是完全，右树不是，那么一定不是
        //右树是完全，左树不是，那么也一定不是
        //右树是完全，右树是完全，那么可能是
        if (leftInfo.isCBT && rightInfo.isCBT) {
            if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
                isCBT = true;
            }
            if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
                isCBT = true;
            }
            if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
                isCBT = true;
            }
        }
    }
    return new Info(isFull, isCBT, height);
}