如何判断一棵二叉树是否完整？

完全二叉树被定义为其中每个级别（可能除了最深的级别）都被完全填充的二叉树。在最深层，所有节点必须尽可能位于左侧。

我认为一个简单的递归算法将能够判断给定的二叉树是否完整，但我似乎无法弄清楚。

如同：

height(t) = if (t==NULL) then 0 else 1+max(height(t.left),height(t.right))

你有：

perfect(t) = if (t==NULL) then 0 else { 
                  let h=perfect(t.left)
                  if (h != -1 && h==perfect(t.right)) then 1+h else -1
             }

如果叶子节点的深度不同，或者任一节点只有一个子节点，则 Perfect(t) 返回 -1；否则，它返回高度。

编辑：这是“完整”=“完美二叉树是一个完整的二叉树，其中所有叶子都处于相同的深度或相同的级别。1（这也被含糊地称为完全二叉树。）”（维基百科).

这是一个递归检查：“完整二叉树是这样的二叉树，其中每个级别（可能除了最后一个级别）都被完全填充，并且所有节点都尽可能远离左侧。”。如果树不完整，则返回 (-1,false)，否则返回 (height,full)，如果是完美的，则 full==true 。

complete(t) = if (t==NULL) then (0,true) else { 
                  let (hl,fl)=complete(t.left)
                  let (hr,fr)=complete(t.right)                      
                  if (fl && hl==hr) then (1+h,fr)
                  else if (fr && hl==hr+1) then (1+h,false)
                  else (-1,false)
              }