摘要：另外，由于篇幅有限，本篇的重點(diǎn)在于二叉樹(shù)的常見(jiàn)算法以及實(shí)現(xiàn)。常見(jiàn)的二叉樹(shù)實(shí)現(xiàn)代碼之前寫(xiě)過(guò)相關(guān)的文章，是關(guān)于如何創(chuàng)建及遍歷二叉樹(shù)的，這里不再贅述。同時(shí)我們注意到，在二叉樹(shù)深度比較大的時(shí)候，我們光是比較左右是不夠的。

本篇為復(fù)習(xí)過(guò)程中遇到過(guò)的總結(jié)，同時(shí)也給準(zhǔn)備面試的同學(xué)一份參考。另外，由于篇幅有限，本篇的重點(diǎn)在于二叉樹(shù)的常見(jiàn)算法以及實(shí)現(xiàn)。

之前寫(xiě)過(guò)相關(guān)的文章，是關(guān)于如何創(chuàng)建及遍歷二叉樹(shù)的，這里不再贅述。提供鏈接給各位感興趣的小伙伴，點(diǎn)此跳轉(zhuǎn)

對(duì)于一棵二叉樹(shù)，翻轉(zhuǎn)它的左右子樹(shù)，如下圖所示：

下面來(lái)分析具體的實(shí)現(xiàn)思路：

對(duì)于根結(jié)點(diǎn)為空的情況

這種情況需要排除，因?yàn)?strong>null不是一個(gè)對(duì)象，不可能存在左右子樹(shù)并且可以翻轉(zhuǎn)的情況

對(duì)于一棵只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)

emmm，這種情況也可以翻轉(zhuǎn)，因?yàn)榇藭r(shí)根結(jié)點(diǎn)左右子樹(shù)為null，交換左右子樹(shù)其實(shí)也就是在交換兩個(gè)null，理論上是翻轉(zhuǎn)了，但實(shí)際上我們看到的和沒(méi)有翻轉(zhuǎn)之前的結(jié)果是一樣的

對(duì)于一棵具有兩個(gè)或兩個(gè)以上結(jié)點(diǎn)的二叉樹(shù)，此時(shí)二叉樹(shù)可以表示為如下的圖像：

可以看出，無(wú)論是只有左子樹(shù)還是只有右子樹(shù)都可以進(jìn)行翻轉(zhuǎn)。這句話等價(jià)于，為空的子樹(shù)可以和不為空的子樹(shù)進(jìn)行交換，也就是不對(duì)為空的子樹(shù)進(jìn)行特殊處理

其實(shí)這樣我們還是不知道二叉樹(shù)是如何翻轉(zhuǎn)的，我們可以用第一張圖的二叉樹(shù)為例子，看一下翻轉(zhuǎn)的具體過(guò)程。

首先我們需要對(duì)根結(jié)點(diǎn)進(jìn)行判空處理，在根結(jié)點(diǎn)不為空的情況下存在左右子樹(shù)（即使左右子樹(shù)為空），然后交換左右子樹(shù)；

把根結(jié)點(diǎn)的左子樹(shù)當(dāng)成左子樹(shù)的根結(jié)點(diǎn)，對(duì)當(dāng)前根結(jié)點(diǎn)進(jìn)行判空處理，不為空時(shí)交換左右子樹(shù);

把根結(jié)的右子樹(shù)當(dāng)成右子樹(shù)的根結(jié)點(diǎn)，對(duì)當(dāng)前根結(jié)點(diǎn)進(jìn)行判空處理，不為空時(shí)交換左右子樹(shù);

重復(fù)步驟2、3，最后二叉樹(shù)變?yōu)樵瓉?lái)的鏡像結(jié)構(gòu),結(jié)果可以參考文章第一張示意圖。

根據(jù)上面的推理過(guò)程我們可以得出如下的代碼：

function reverseTree(root){
    if( root !== null){
        [root.left, root.right] = [root.right, root.left]
        reverseTree(root.left)
        reverseTree(root.right)
    }
}

雖然推理過(guò)程比較復(fù)雜（也可能是寫(xiě)的比較啰嗦。。），但是仔細(xì)觀察代碼，這和遍歷的代碼似乎也沒(méi)多大差別，只是把輸出結(jié)點(diǎn)變?yōu)榱私粨Q結(jié)點(diǎn)。

一棵左右完全對(duì)稱(chēng)的二叉樹(shù)是這樣的：

那到底如何判斷呢？

根結(jié)點(diǎn)為空時(shí)，此時(shí)為一棵空二叉樹(shù)，滿足對(duì)稱(chēng)條件（-_-||）

只有一個(gè)根結(jié)點(diǎn)時(shí)，左右子樹(shù)都為null，滿足左右對(duì)稱(chēng)條件

只有兩個(gè)結(jié)點(diǎn)時(shí)，此時(shí)左右子樹(shù)必定有一個(gè)為空，不可能存在對(duì)稱(chēng)的情況

結(jié)點(diǎn)數(shù)在三個(gè)及三個(gè)以上時(shí)，二叉樹(shù)有對(duì)稱(chēng)的可能。

按照我們正常的思維，看對(duì)稱(chēng)與否，首先看左邊，然后看右邊，最后比較左右是否相等。同時(shí)我們注意到，在二叉樹(shù)深度比較大的時(shí)候，我們光是比較左右是不夠的。可以觀察到，我們比較完左右以后還需要比較左的左和右的右，比較左的右和右的左

這么看是比較繞，接下來(lái)我們來(lái)看圖分析：

先比較根結(jié)點(diǎn)左右孩子

將左子樹(shù)根結(jié)點(diǎn)的左孩子與右子樹(shù)根結(jié)點(diǎn)的右孩子進(jìn)行比較

將左子樹(shù)根結(jié)點(diǎn)的右孩子與右子樹(shù)根結(jié)點(diǎn)的左孩子進(jìn)行比較

重復(fù)以上過(guò)程...

function isSymmetrical(pRoot)
{
    // write code here
    if(!pRoot){
        return true
    }
    return funC(pRoot.left, pRoot.right)
}
 
function funC(left, right){
     
    if(!left){
        return right === null
    }
     
    if(!right){
        return false
    }
     
    if(left.val !== right.val){
        return false
    }
     
    return funC(left.right, right.left) && funC(left.left, right.right)
}

只有一個(gè)根結(jié)點(diǎn)時(shí)，二叉樹(shù)深度為1

只有左子樹(shù)時(shí)，二叉樹(shù)深度為左子樹(shù)深度加1

只有右子樹(shù)時(shí)，二叉樹(shù)深度為右子樹(shù)深度加1

同時(shí)存在左右子樹(shù)時(shí)，二叉樹(shù)深度為左右子樹(shù)中深度最大者加1

function deep(root){
    if(!root){
        return 0
    }
    let left = deep(root.left)
    let right = deep(root.right)
    return left > right ? left + 1 : right + 1
}

二叉樹(shù)的寬度是啥？我把它理解為具有最多結(jié)點(diǎn)數(shù)的層中包含的結(jié)點(diǎn)數(shù)，比如下圖所示的二叉樹(shù)，其實(shí)它的寬度就是為4：

根據(jù)上圖，我們?nèi)绾嗡愠龆鏄?shù)的寬度呢？其實(shí)有個(gè)很簡(jiǎn)單的思路：

算出第一層的結(jié)點(diǎn)數(shù)，保存

算出第二層的結(jié)點(diǎn)數(shù)，保存一二層中較大的結(jié)點(diǎn)數(shù)

重復(fù)以上過(guò)程

根據(jù)分析過(guò)程，我們可以利用隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)這個(gè)算法，代碼如下：

function width(root){
    if(!root){
        return 0
    }
    let queue = [root], max = 1, deep = 1
    while(queue.length){
        while(deep--){
            let temp = queue.shift()
            if(temp.left){
                queue.push(temp.left)
            }
            if(temp.right){
                queue.push(temp.right)
            }
        }
        deep = queue.length
        max = max > deep ? max : deep
    }
    return max
}

前序遍歷：

前序遍歷首先訪問(wèn)根結(jié)點(diǎn)然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。

中序遍歷：

中序遍歷首先訪問(wèn)左子樹(shù)然后遍歷根節(jié)點(diǎn)，最后遍歷右子樹(shù)。

后序遍歷：

后序遍歷首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)

根據(jù)前序遍歷產(chǎn)生的序列和中序遍歷產(chǎn)生的序列生成一顆二叉樹(shù)

假如有這么一棵二叉樹(shù)：

可以看出它前序遍歷序列為：8 6 5 7 10 9 11，中序遍歷序列為：5 6 7 8 9 10 11
其中有個(gè)很明顯的特征，根結(jié)點(diǎn)的值為前序遍歷序列的第一個(gè)值，而且我們?cè)?strong>中序遍歷序列中很容易看出，根結(jié)點(diǎn)左右兩邊的結(jié)點(diǎn)分別為構(gòu)成左子樹(shù)和右子樹(shù)的結(jié)點(diǎn)，所以我們可以得到一種解決問(wèn)題的思路：

獲取前序遍歷的第一個(gè)值，構(gòu)建根結(jié)點(diǎn)

生成左子樹(shù)的前序遍歷序列和中序遍歷序列

生成右子樹(shù)的前序遍歷序列和中序遍歷序列

重復(fù)以上過(guò)程...

function reConstructBinaryTree(pre, vin)
{
    if(!pre || !vin || !pre.length || !vin.length){
        return null
    }
    let root = new TreeNode(pre[0]),
        tIndex = vin.indexOf(pre[0]),
        leftIn = [],leftPre = [],rightIn = [],rightPre = []
    
    for(let i = 0; i < tIndex; i++){
        leftIn.push(vin[i])
        leftPre.push(pre[i+1])
    }
    for(let i = tIndex+1; i < pre.length; i++){
        rightIn.push(vin[i])
        rightPre.push(pre[i])
    }
    //遞歸
    root.left = reConstructBinaryTree(leftPre, leftIn)
    root.right = reConstructBinaryTree(rightPre, rightIn)
    return root
}

以上思路、代碼有錯(cuò)漏請(qǐng)?jiān)谠u(píng)論區(qū)指出！

代碼部分來(lái)自牛客網(wǎng)--劍指offer，相應(yīng)的題目也都可以在上面找到。

掃描下方的二維碼或搜索「tony老師的前端補(bǔ)習(xí)班」關(guān)注我的微信公眾號(hào)，那么就可以第一時(shí)間收到我的最新文章。