簡(jiǎn)單來(lái)說(shuō), 完全二叉樹(shù)是指按照層次進(jìn)行遍歷的時(shí)候所得到的序列與滿二叉樹(shù)相對(duì)應(yīng)

這里提供兩種思路和相應(yīng)的代碼:

1. 利用與滿二叉樹(shù)的對(duì)應(yīng)關(guān)系

任意的一個(gè)完全二叉樹(shù), 都可以補(bǔ)上一些空節(jié)點(diǎn)來(lái)形成一棵滿二叉樹(shù), 當(dāng)然了, 這些補(bǔ)上的節(jié)點(diǎn)都是葉子節(jié)點(diǎn).我們假設(shè)這些補(bǔ)上的節(jié)點(diǎn)為空節(jié)點(diǎn), 那么在對(duì)這棵補(bǔ)成滿二叉樹(shù)的樹(shù)進(jìn)行層次遍歷的時(shí)候, 那些補(bǔ)上的空節(jié)點(diǎn)都一定會(huì)出現(xiàn)在遍歷序列的結(jié)尾, 就是一系列的原節(jié)點(diǎn)后面跟著一系列補(bǔ)上的空節(jié)點(diǎn), 不會(huì)交替出現(xiàn). 利用上述性質(zhì), 可以肯定, 如果空節(jié)點(diǎn)和原節(jié)點(diǎn)交替出現(xiàn)了, 那么這棵樹(shù)一定不是完全二叉樹(shù).

// 由于如何用程序比較簡(jiǎn)單的實(shí)現(xiàn)把二叉樹(shù)補(bǔ)滿, 我暫時(shí)沒(méi)有思路...

2. 根據(jù)完全二叉樹(shù)的性質(zhì)在層次遍歷的過(guò)程中做判斷

具體流程如下:

1. 對(duì)二叉樹(shù)進(jìn)行層次遍歷
2. 如果當(dāng)前節(jié)點(diǎn)有右孩子, 沒(méi)有左孩子, 返回 false
3. 如果當(dāng)前節(jié)點(diǎn)有左孩子, 沒(méi)有右孩子, 那么之后的節(jié)點(diǎn)都必須為葉子節(jié)點(diǎn)(即沒(méi)有孩子), 否則返回 false
4. 遍歷過(guò)程中如果不返回 false, 遍歷結(jié)束后返回 true

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

    /*
     * 層次遍歷過(guò)程中對(duì)每個(gè)節(jié)點(diǎn)執(zhí)行的操作
     *
     * @param node - 當(dāng)前節(jié)點(diǎn)
     */
    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
        }
    }
}