题解 | #判断是不是完全二叉树#

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类
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        // write code here

        // 算法的时间复杂度O(N)，额外空间复杂度O(N)

        // 1.数据准备
        // 1.1 创建队列，用于层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        // 1.2 创建数组，用于存储结点序号及其本身（同时保留结点的父子关系），因为有序所以方便遍历
        LinkedList<TreeNode> list = new LinkedList<>();
        // 1.3 创建哈希表，用于根据结点查询其序号
        HashMap<TreeNode, Integer> map = new HashMap<>();

        // 2.层序遍历，写入数据结构
        // 2.1 头结点先入队
        queue.add(root);
        // 2.2 利用队列层序遍历
        int number = 0;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            // 2.3 分配编号，写入数据结构
            list.add(cur);
            map.put(cur, number);
            // 2.4 子节点入队
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
            // 2.5序号自增
            number++;
        }

        // 3.验证完全二叉树 - i -> 2i + 1 / 2i + 2
        for (TreeNode cur : list) {
            // 3.1 通过HashMap获得当前结点的序号
            int curNo = map.get(cur);
            // 3.2 分别获得其左右子结点，验证序号是否满足2i + 1 / 2i + 2
            if (cur.left != null) {
                int leftNo = map.get(cur.left);
                if (leftNo != (2 * curNo + 1)) {
                    // 3.3 若当前结点不满足，则直接返回false
                    return false;
                }
            }
            if (cur.right != null) {
                int rightNo = map.get(cur.right);
                if (rightNo != (2 * curNo + 2)) {
                    // 3.3 若当前结点不满足，则直接返回false
                    return false;
                }
            }
        }
        // 3.4 若每个结点都满足，则返回true
        return true;
    }
}