[二叉树] 判断二叉树是否是完全二叉树

简单来说, 完全二叉树是指按照层次进行遍历的时候所得到的序列与满二叉树相对应

这里提供两种思路和相应的代码:

1. 利用与满二叉树的对应关系

任意的一个完全二叉树, 都可以补上一些空节点来形成一棵满二叉树, 当然了, 这些补上的节点都是叶子节点.我们假设这些补上的节点为空节点, 那么在对这棵补成满二叉树的树进行层次遍历的时候, 那些补上的空节点都一定会出现在遍历序列的结尾, 就是一系列的原节点后面跟着一系列补上的空节点, 不会交替出现. 利用上述性质, 可以肯定, 如果空节点和原节点交替出现了, 那么这棵树一定不是完全二叉树.

// 由于如何用程序比较简单的实现把二叉树补满, 我暂时没有思路...

2. 根据完全二叉树的性质在层次遍历的过程中做判断

具体流程如下:

1. 对二叉树进行层次遍历
2. 如果当前节点有右孩子, 没有左孩子, 返回 false
3. 如果当前节点有左孩子, 没有右孩子, 那么之后的节点都必须为叶子节点(即没有孩子), 否则返回 false
4. 遍历过程中如果不返回 false, 遍历结束后返回 true

function isCompleteBinaryTree(root)
{
    let result = true
    let leaf
    root.levelIterate(function(node)
    {
        if( ! touch(node))
        {
            result = false
            return false // 终止遍历
        }
    })
    return result

    /*
     * 层次遍历过程中对每个节点执行的操作
     *
     * @param node - 当前节点
     */
    function touch(node)
    {
        if(leaf)
        {
            return ( ! node.left) && ( ! node.right)
        }
        else
        {
            if(node.right && ! node.left)
            {
                return false
            }

            if(node.left && ! node.right)
            {
                leaf = true
            }

            // node.left && node.right
            return true
        }
    }
}