A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

A complete binary tree is just like a full binary tree, but with two major differences

1. All the leaf elements must lean towards the left.
2. The last leaf element might not have a right sibling i.e. a complete binary tree doesn’t have to be a full binary tree.

Following is the sample of a complete binary tree.

Given the root of a binary tree, check whether it’s a complete binary tree or not.

数据结构和算法：初级练习题 #32 – 完全二叉树

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

上面的图例里面是一颗完全二叉树。

给定一颗二叉树，检查它是否是完全二叉树。

算法思路范例：
判断一棵树是否是完全二叉树的思路：
– 如果树为空，则直接返回错
– 如果树不为空：层序遍历二叉树
– 如果一个结点左右子节点都不为空，则删除该节点，将其左右子节点加入队列；
– 如果遇到一个节点，左子节点为空，右子节点不为空，则该树一定不是完全二叉树；
– 如果遇到一个节点，左子节点不为空，右子节点为空；或者左右子节点都为空；则该节点之后的队列中的节点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树；

Python Solution