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

思路：根据题意，完全二叉树除了最后一层叶子节点层可以缺少右侧的节点，其余层必须满节点，不能中间缺节点。
这里符合树的广度优先访问方式来处理，从根节点层往下到叶子节点层，判断非叶子节点层是否满足满节点条件，叶子节点层是否左侧没有跳缺节点。每层节点从左往右遍历，并验证下一层节点是否满足上述左侧无跳缺条件，递归调用函数。



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
        if (root == null) {
            return true;
        }
        int lv = 0;
        List<TreeNode> treeNodesLv = new ArrayList<>();
        treeNodesLv.add(root); 
        return isCompleteTreeLv(treeNodesLv, 0);
    }

    public boolean isCompleteTreeLv(List<TreeNode> treeNodesLv, int lv) {
        int maxNodes = 1 << lv;
        if (treeNodesLv.size() == maxNodes) {
            // 满节点层，遍历判别，构建递归访问下层节点的参数
            List<TreeNode> nextTreeNodes = new ArrayList<>();
            boolean prenull = false;
            for (TreeNode t : treeNodesLv) {
                if (prenull) {
                    if(t.right != null || t.left != null) {
                        return false;
                    }
                } else {
                    if(t.left != null && t.right != null) {
                        nextTreeNodes.add(t.left);
                        nextTreeNodes.add(t.right);
                    } else if (t.left == null && t.right == null) {
                        prenull = true;
                    } else if (t.left != null && t.right == null) {
                        prenull = true;
                        nextTreeNodes.add(t.left);
                    } else if (t.left == null && t.right != null) {
                        return false;
                    }
                }
            }
            return isCompleteTreeLv(nextTreeNodes, lv + 1);

        } else {
            // 已达叶子节点层判别条件（只有叶子几点层允许节点不满）
            for (TreeNode t : treeNodesLv) {
                if (t.left != null || t.right != null) {
                    return false;
                }
            }
            return true;
        }   

    }
}