leetcode.cn/problems/check-completeness-of-a-binary-tree/" rel="nofollow">958. 二叉树的完全性检验

1. 思路

判断是否为完全二叉树的两个条件：

1. 如果节点有右孩子，没有左孩子，一定不是完全二叉树
2. 如果节点的孩子不全，那么后续的节点必须为叶子节点才是完全二叉树，否则不是。（上图中d节点只有左孩子，因此d节点之后的节点都是叶子节点）

2. 代码

java">public static int MAXN = 101;
public static TreeNode[] queue = new TreeNode[MAXN];
public static int l ,r;public static boolean isCompleteTree(TreeNode root) {if (root == null){return true;}l = r = 0;queue[r++] = root;boolean leaf = false;while (l < r){TreeNode poll = queue[l++];if ((poll.left == null && poll.right != null) || (leaf && (poll.left != null || poll.right != null))){return false;}if (poll.left != null){queue[r++] = poll.left;}if (poll.right != null){queue[r++] = poll.right;}if(poll.left == null || poll.right == null){leaf = true;}}return true;
}