什么是二叉樹枣接？

引用自百度百科：
在計(jì)算機(jī)科學(xué)中，二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree），同樣的左右子樹也都是二叉樹.

前言

本文代碼實(shí)現(xiàn)為 C/C++彭沼，因?yàn)椴皇且粋€(gè)完整的講解文章，只是個(gè)人思路备埃，所以說思路講解可能有不足之處姓惑，有錯(cuò)誤請指出.

節(jié)點(diǎn)定義

使用單向鏈表的形式，只保存當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)和權(quán)值按脚，不保存父節(jié)點(diǎn).

typedef struct Node{
    int value;//權(quán)值于毙，根據(jù)實(shí)際情況而定，這里用數(shù)字
    Node *lChild;//左兒子節(jié)點(diǎn)
    Node *rChild;//右兒子節(jié)點(diǎn)
}BNode;

二叉樹的遍歷

二叉樹的遍歷分為三種：

• 前序遍歷
  先遍歷當(dāng)前節(jié)點(diǎn)(根節(jié)點(diǎn))辅搬，然后遍歷左兒子節(jié)點(diǎn)唯沮，再遍歷右兒子節(jié)點(diǎn)
• 中序遍歷
  先遍歷左兒子節(jié)點(diǎn)，然后遍歷當(dāng)前節(jié)點(diǎn)(根節(jié)點(diǎn))堪遂，再遍歷右兒子節(jié)點(diǎn)
• 后序遍歷
  先遍歷左兒子節(jié)點(diǎn)介蛉，然后遍歷右兒子節(jié)點(diǎn)，再遍歷當(dāng)前節(jié)點(diǎn)(根節(jié)點(diǎn))

我們創(chuàng)建二叉樹的時(shí)候一般用的是遞歸的方法溶褪，但是二叉樹的遍歷可以有遞歸和非遞歸兩種方式.下面會(huì)分別給出二叉樹遍歷遞歸和非遞歸的思路和代碼.

PS：建議看懂思路后再看代碼實(shí)現(xiàn)币旧，然后手動(dòng)模擬一下，效果更佳.

前序遍歷

遞歸版:
先遍歷根節(jié)點(diǎn)猿妈，然后遍歷左子樹吹菱，再遍歷右子樹
非常經(jīng)典的遞歸思想，理解二叉樹的性質(zhì)和遞歸思想即可得出.

void preorderTraversal(BNode *rootNode) {
    if(rootNode != NULL) {
        printf("%d ", rootNode->value);
        preorderTraversal(rootNode->lChild);
        preorderTraversal(rootNode->rChild);
    }
}

非遞歸版:

使用棧來實(shí)現(xiàn)于游，因?yàn)?C++ 中有現(xiàn)成的庫，所以說就不手動(dòng)模擬棧了垫言，當(dāng)遍歷到一個(gè)節(jié)點(diǎn)的時(shí)候贰剥，先將此節(jié)點(diǎn)輸出，然后一直遍歷其左兒子筷频，依次循環(huán)蚌成，直到碰到葉子節(jié)點(diǎn)，然后開始彈凛捏，也就是遞歸過程中的回溯担忧。

對于任一結(jié)點(diǎn)node：

• 訪問結(jié)點(diǎn)node，并將結(jié)點(diǎn)node入棧;
• 判斷結(jié)點(diǎn)node的左孩子是否為空
• 若為空坯癣，則取棧頂結(jié)點(diǎn)并進(jìn)行出棧操作瓶盛，并將棧頂結(jié)點(diǎn)的右孩子置為當(dāng)前的結(jié)點(diǎn)node，循環(huán)至1
• 若不為空，則將node的左孩子置為當(dāng)前的結(jié)點(diǎn)node;
• 直到node為NULL并且棧為空惩猫，則遍歷結(jié)束芝硬。

void preorderTraversalNonrecursive(BNode *rootNode) {
    stack<BNode *>s;
    if (rootNode == NULL ) {
        return ;
    }
    BNode *tempNode = rootNode;
    while(!s.empty() || tempNode != NULL) {
        while(tempNode != NULL) {
            printf("%d ", tempNode->value);
            s.push(tempNode);
            tempNode = tempNode->lChild;
        }
        if (!s.empty()) {
            tempNode = s.top();
            s.pop();
            tempNode = tempNode->rChild;
        }
    }
}

中序遍歷

遞歸版：
先遍歷左子樹，然后遍歷根節(jié)點(diǎn)轧房，再遍歷右子樹

void inorderTraversal(BNode *rootNode) {
    if(rootNode != NULL) {
        inorderTraversal(rootNode->lChild);
        printf("%d ", rootNode->value);
        inorderTraversal(rootNode->rChild);
    }
}

非遞歸版：
和先序遍歷一樣的思想拌阴，因?yàn)橐仍L問左子樹，然后再訪問根節(jié)點(diǎn)(當(dāng)前節(jié)點(diǎn))奶镶，那么在棧彈出的時(shí)候進(jìn)行輸出即為所求.

對于任一結(jié)點(diǎn)node：

• 若其左孩子不為空迟赃，則將node入棧并將node的左孩子置為當(dāng)前的node，然后對當(dāng)前結(jié)點(diǎn)P再進(jìn)行相同的處理纤壁；
• 若其左孩子為空，則取棧頂元素并進(jìn)行出棧操作摄乒，訪問該棧頂結(jié)點(diǎn)，然后將當(dāng)前的node置為棧頂結(jié)點(diǎn)的右孩子馍佑；
• 直到node為NULL并且棧為空則遍歷結(jié)束

void inorderTraversalNonrecursive(BNode *rootNode) {
    stack<BNode *>s;
    if (rootNode == NULL ) {
        return ;
    }
    BNode *tempNode = rootNode;
    while(!s.empty() || tempNode != NULL) {
        while(tempNode != NULL) {
            s.push(tempNode);
            tempNode = tempNode->lChild;
        }
        if (!s.empty()) {
            tempNode = s.top();
            s.pop();
            printf("%d ", tempNode->value);
            tempNode = tempNode->rChild;
        }
    }
}

后序遍歷

遞歸版：
先遍歷左子樹梨水，然后遍歷右子樹，再遍歷根節(jié)點(diǎn)

void postorderTraversal(BNode *rootNode) {
    if(rootNode != NULL) {
        postorderTraversal(rootNode->lChild);
        postorderTraversal(rootNode->rChild);
        printf("%d ", rootNode->value);
    }
}

非遞歸版：
后序遍歷的非遞歸版和先序遍歷疫诽、中序遍歷不一樣，這里我用兩個(gè)棧來實(shí)現(xiàn)奇徒，一個(gè)棧來保存遍歷節(jié)點(diǎn)并不斷的進(jìn)行彈出雏亚，一個(gè)棧來保存節(jié)點(diǎn)的遍歷順序，最后遍歷第二個(gè)棧.

void postorderTraversalNonrecursive(BNode *rootNode) {
    stack<BNode *>s1;
    stack<BNode *>s2;
    if (rootNode == NULL ) {
        return ;
    }
    s1.push(rootNode);
    while(!s1.empty()) {
        BNode *tempNode = s1.top();
        s1.pop();
        s2.push(tempNode);
        if (tempNode->lChild) {
            s1.push(tempNode->lChild);
        }
        if (tempNode->rChild) {
            s1.push(tempNode->rChild);
        }
    }
    while(!s2.empty()) {
        printf("%d ", s2.top()->value);
        s2.pop();
    }
}

分層遍歷二叉樹

即每次輸出二叉樹的一層摩钙，例如：

實(shí)現(xiàn)思路：廣度優(yōu)先遍歷(BFS)罢低，使用隊(duì)列來實(shí)現(xiàn)，每次遍歷當(dāng)前節(jié)點(diǎn)的左右兒子節(jié)點(diǎn)胖笛，并將其加入隊(duì)列中网持，然后進(jìn)行隊(duì)列的彈出直到隊(duì)列為空.

void levelTraversal(BNode *rootNode) {
    queue<BNode *>q;
    q.push(rootNode);
    while(!q.empty()) {
        BNode *tempNode = q.front();
        q.pop();
        printf("%d ", tempNode->value);
        if (tempNode->lChild) {
            q.push(tempNode->lChild);
        }
        if (tempNode->rChild) {
            q.push(tempNode->rChild);
        }
    }
}

S型打印二叉樹

這里我使用的是隊(duì)列 + 棧來實(shí)現(xiàn)的，隊(duì)列存儲(chǔ)當(dāng)前遍歷的節(jié)點(diǎn)的序列长踊，棧中存儲(chǔ)下一層遍歷的節(jié)點(diǎn)順序功舀，使用一個(gè) level 來判斷遍歷方向

void STraversal(BNode *rootNode) {
    queue<BNode *>q;
    stack<BNode *>s;
    int level = 1;//根節(jié)點(diǎn)為第一層
    q.push(rootNode);
    while(!q.empty()){
        BNode *temp;
        while(!q.empty()){
            temp = q.front();
            printf("%d ", temp->value);
            if (level % 2) {//下一層要從左到右遍歷
                if (temp->rChild != NULL) {
                    s.push(temp->rChild);
                }
                if (temp->lChild != NULL) {
                    s.push(temp->lChild);
                }
            } else {//下一層要從右到左遍歷
                if (temp->lChild != NULL) {
                    s.push(temp->lChild);
                }
                if (temp->rChild != NULL) {
                    s.push(temp->rChild);
                }
            }
            q.pop();
        }
        while(!s.empty()){
            temp = s.top();
            //將下一層節(jié)點(diǎn)的按照遍歷順序加入隊(duì)列中
            q.push(temp);
            s.pop();
        }
        level++;
    }
}

二叉樹深度

一棵空樹的深度為0，只有根節(jié)點(diǎn)的數(shù)的深度為1身弊，所以說一個(gè)數(shù)的深度 = max(左子樹的深度辟汰，右子樹的深度) + 1(當(dāng)前節(jié)點(diǎn))列敲，使用遞歸來求.

int findDeepOfTree(BNode *rootNode){
    if(rootNode == NULL){
        return 0;
    }
    return max(findDeepOfTree(rootNode->lChild), findDeepOfTree(rootNode->rChild)) + 1;
}

樹的寬度

樹的寬度即是節(jié)點(diǎn)最多的一層的節(jié)點(diǎn)數(shù)，根據(jù)前面分層遍歷二叉樹的原理莉擒，每次從隊(duì)列中取出一層的節(jié)點(diǎn)酿炸，將其子節(jié)點(diǎn)加入隊(duì)列，然后查看節(jié)點(diǎn)數(shù)涨冀，即隊(duì)列的大小.

int findWidthOfTree(BNode *rootNode){
    queue<BNode *>q;
    q.push(rootNode);
    int ansWidth = 1;
    while(!q.empty()) {
        for(int i = 0; i < q.size(); i++) {
            BNode *tempNode = q.front();
            q.pop();
            if (tempNode->lChild) {
                q.push(tempNode->lChild);
            }
            if (tempNode->rChild) {
                q.push(tempNode->rChild);
            }
        }
        ansWidth = max(ansWidth, (int)q.size());
    }
    return ansWidth;
}

求葉子節(jié)點(diǎn)數(shù)

葉子節(jié)點(diǎn)填硕，即不含子節(jié)點(diǎn)的節(jié)點(diǎn)，當(dāng)一個(gè)節(jié)點(diǎn)的左右兒子皆為空的時(shí)候鹿鳖，此節(jié)點(diǎn)為葉子節(jié)點(diǎn)扁眯，所以可以得出：樹的葉子節(jié)點(diǎn)數(shù) = 左子樹的葉子節(jié)點(diǎn)數(shù) + 右子樹的葉子節(jié)點(diǎn)數(shù).

int findNumOfLeafNode(BNode *rootNode){
    if(rootNode == NULL) {
        return 0;
    }
    if(rootNode->lChild == NULL && rootNode->rChild == NULL) {
        return 1;
    }
    return findNumOfLeafNode(rootNode->lChild) + findNumOfLeafNode(rootNode->rChild);
}

求樹的一層有多少節(jié)點(diǎn)

根節(jié)點(diǎn)某層的節(jié)點(diǎn)數(shù) = 左子樹中某層的節(jié)點(diǎn)數(shù) + 右子樹中某層的節(jié)點(diǎn)數(shù)

設(shè)置一個(gè)層數(shù)變量 level，在遞歸過程中翅帜，通過 level 的減小模擬下降的過程姻檀，當(dāng)level = 1的時(shí)候說明到達(dá)了我們要找的那一層，那么返回當(dāng)前節(jié)點(diǎn)數(shù)涝滴，也就是1.

int findNumOfNodeOnLevel(BNode *rootNode, int level) {
    if (level == 0 || rootNode == NULL) {
        return 0;
    }
    if(level == 1){
        return 1;
    }
    return findNumOfNodeOnLevel(rootNode->lChild, level - 1) + findNumOfNodeOnLevel(rootNode->rChild, level - 1);
}

求樹的直徑(樹上兩個(gè)節(jié)點(diǎn)間的最大距離)

這里有兩種方案：

方案一：

直接遍歷每個(gè)點(diǎn)绣版，模擬當(dāng)前點(diǎn)為兩個(gè)節(jié)點(diǎn)路徑的轉(zhuǎn)折點(diǎn)時(shí)的最大距離，那么也就是當(dāng)前節(jié)點(diǎn)的左子樹深度 + 右子樹深度歼疮，然后取最大值

時(shí)間復(fù)雜度： O(n^2)

int findDiameterOfTree1(BNode *rootNode) {
    if(rootNode == NULL) {
        return 0;
    }
    return max(max(findDiameterOfTree1(rootNode->lChild), findDiameterOfTree1(rootNode->rChild)), findDeepOfTree(rootNode->lChild) + findDeepOfTree(rootNode->rChild));
}

方案二：

在求子樹深度的時(shí)候就將最長距離求出

int findMaxDeep(BNode *rootNode, int &ans) {
    if (rootNode == NULL) {
        return 0;
    }
    int leftDeep = findMaxDeep(rootNode->lChild, ans);
    int rightDeep = findMaxDeep(rootNode->rChild, ans);
    ans = max(ans, leftDeep + rightDeep);
    return max(leftDeep, rightDeep) + 1;
}
int findDiameterOfTree2(BNode *rootNode) {
    int ans = 0;
    findMaxDeep(rootNode, ans);
    return ans;
}

求一個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑

定義一個(gè)從某節(jié)點(diǎn)到根節(jié)點(diǎn)的棧韩脏，這里使用 vector 來實(shí)現(xiàn)，具體步驟：

• 將當(dāng)前節(jié)點(diǎn)壓入棧中
• 尋找當(dāng)前節(jié)點(diǎn)左子樹是否含有要尋找節(jié)點(diǎn)(遞歸進(jìn)行)
  • 如果有杭朱，棧中存放的就是路徑
  • 如果沒有弧械，再尋找右子樹是否含有要尋找節(jié)點(diǎn)
    • 如果有刃唐，棧中存放的就是路徑
    • 如果都沒有唁桩，彈出當(dāng)前節(jié)點(diǎn)耸棒，在遍歷棧中的上一個(gè)節(jié)點(diǎn)

bool findPathFromNodetoRoot(BNode *rootNode, BNode *node, vector<BNode *> &path) {
    if (rootNode == NULL || node == NULL) {
        return false;
    }
    path.push_back(rootNode);
    if (rootNode == node) {
        return true;
    }
    bool isFind = findPathFromNodetoRoot(rootNode->lChild, node, path);
    if (isFind == false) {
        isFind = findPathFromNodetoRoot(rootNode->rChild, node, path);
    }
    if (isFind == false) {
        path.pop_back();
    }
    return isFind;
}

求兩個(gè)節(jié)點(diǎn)的最近公共祖先

如果當(dāng)前遍歷到了一個(gè)根節(jié)點(diǎn)单山，那么檢查我們要查找的兩個(gè)節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)的哪個(gè)子樹中米奸，會(huì)有三種情況：

• 都在左子樹
• 都在右子樹
• 一個(gè)在左子樹悴晰，一個(gè)在右子樹

情況一和情況二的時(shí)候我們需要返回節(jié)點(diǎn)所在子樹的遍歷結(jié)果铡溪，情況三的時(shí)候說明我們已經(jīng)找到了最近公共祖先(不明白的最好手動(dòng)模擬一下)泪喊。

BNode * findCommonNodeOfTwoNode(BNode *rootNode, BNode *node1, BNode *node2) {
    if (rootNode == NULL || node1 == NULL || node2 == NULL) {
        return NULL;
    }
    if (node1 == rootNode || node2 == rootNode) {
        return rootNode;
    }
    BNode *leftLCANode = findCommonNodeOfTwoNode(rootNode->lChild, node1, node2);//檢查左子樹
    BNode *rightLCANode = findCommonNodeOfTwoNode(rootNode->rChild, node1, node2);//檢查右子樹
    if (leftLCANode != NULL && rightLCANode != NULL) {//一個(gè)在左一個(gè)在右袒啼，找到目標(biāo)
        return rootNode;
    }
    if (leftLCANode == NULL) {//全在右子樹
        return rightLCANode;
    } else {//全在左子樹
        return leftLCANode;
    }
}

還有一種方案就是將兩個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑都求出蚓再，然后開始對比，如果遇到第一個(gè)相同的節(jié)點(diǎn)即為所求赦邻，這個(gè)留給讀者自己實(shí)現(xiàn)吧.

求兩個(gè)節(jié)點(diǎn)間的路徑

分別將兩個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑求出惶洲，然后對根節(jié)點(diǎn)到兩個(gè)節(jié)點(diǎn)的最近公共祖先節(jié)點(diǎn)的路徑進(jìn)行去重即可.

void findPathBetweenTwoNode(BNode *rootNode, BNode *node1, BNode *node2, vector<BNode *> &path){
    vector<BNode *>path1;
    findPathFromNodetoRoot(rootNode, node1, path1);
    vector<BNode *>path2;
    findPathFromNodetoRoot(rootNode, node2, path2);

    vector<BNode *>::iterator it1 = path1.begin();
    vector<BNode *>::iterator it2 = path2.begin();
    BNode *LCANode;
    int cnt = 0;
    //去重
    while(it1 != path1.end() && it2 != path2.end()) {
        if (*it1 == *it2) {
            LCANode = *it1;
            cnt++;
        }
        it1++;
        it2++;
    }
    for(int i = cnt - 1; i < path1.size(); i++) {
        path.push_back(path1[i]);
    }
    reverse(path.begin(), path.end());
    for(int i = cnt; i < path2.size(); i++) {
        path.push_back(path2[i]);
    }
}

翻轉(zhuǎn)二叉樹

這里穿插一個(gè)小故事恬吕，2015 年 6 月 10 日铐料，Homebrew 的作者 Max Howell 在 twitter 上發(fā)表了如下一內(nèi)容：

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

大概意思就是：他在應(yīng)聘谷歌的時(shí)候被面試官說：雖然有90%的人在用你寫的軟件钠惩，但是你不會(huì)翻轉(zhuǎn)二叉樹篓跛，所以說我們不會(huì)錄用你.
因?yàn)?Max Howell 的影響力坦刀，所以這件事情一下子廣為流傳.

回到正題：翻轉(zhuǎn)二叉樹，即是二叉樹的鏡像林艘，也就是將二叉樹的左右子樹對調(diào)狐援，這里有兩種方案;

遞歸版：

void swapTree(BNode *&root){
    BNode *tmp = root->lChild;
    root->lChild = root->rChild;
    root->rChild = tmp;
}
void turnBTree(BNode *rootNode) {
    if (rootNode == NULL) {
        return ;
    }
    turnBTree(rootNode->lChild);
    turnBTree(rootNode->rChild);
    swapTree(rootNode);
}

非遞歸版：

void invertBinaryTreeNonrecursive2(BNode *root) {
    if(root == NULL){
        return ;
    }
    stack<BNode *>s;
    s.push(root);
    while(!s.empty())
    {
        BNode *tmp = s.top();
        s.pop();
        swapTree(tmp);
        if(tmp->lChild){
            s.push(tmp->lChild);
        }
        if(tmp->rChild){
            s.push(tmp->rChild);
        }
    }
}

判斷完全二叉樹

完全二叉樹即葉節(jié)點(diǎn)只能出現(xiàn)在最下層和次下層咕村，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置的二叉樹

所以可得出判斷的兩個(gè)條件：

• 如果某個(gè)節(jié)點(diǎn)的右子樹不為空懈涛，則它的左子樹必須不為空
• 如果某個(gè)節(jié)點(diǎn)的右子樹為空批钠，則排在它后面的節(jié)點(diǎn)必須沒有孩子節(jié)點(diǎn)

所以我們可以設(shè)置一個(gè)標(biāo)志位flag得封，當(dāng)子樹滿足完全二叉樹時(shí)忙上，設(shè)置flag=YES疫粥。當(dāng)flag=YES而節(jié)點(diǎn)又破壞了完全二叉樹的條件，那么它就不是完全二叉樹项秉。

bool checkIsCompleteBTree(BNode *rootNode) {
    if (rootNode == NULL) {
        return true;
    }
    queue<BNode *>q;
    q.push(rootNode);
    bool flag = false;
    while(!q.empty()){
        BNode *tempNode = q.front();
        q.pop();
        if (tempNode->lChild == NULL && tempNode->rChild != NULL) {
            return false;
        }
        if (tempNode->lChild == NULL && tempNode->rChild == NULL) {
            flag = true;
        }
        if (flag == true && tempNode->lChild != NULL && tempNode->rChild != NULL) {
            return false;
        }
        if (tempNode->lChild != NULL) {
            q.push(tempNode->lChild);
        }
        if (tempNode->rChild != NULL) {
            q.push(tempNode->rChild);
        }
    }
    return flag;
}

判斷平衡二叉樹

又被稱為AVL樹（有別于AVL算法），且具有以下性質(zhì)：它是一 棵空樹或它的左右兩個(gè)子樹的高度差的絕對值不超過1岁诉，并且左右兩個(gè)子樹都是一棵平衡二叉樹.
遞歸檢查每個(gè)節(jié)點(diǎn)的左右子樹的高度之差是否符合要求跋选，返回即可.

bool checkLR(BNode *rootNode, int &height) {
    if (rootNode == NULL) {
        return true;
    }
    if (rootNode->value > rootNode->rChild->value || rootNode->value < rootNode->lChild->value) {
        return false;
    }
    bool lAns = checkLR(rootNode->lChild, height);
    int lHeight = height;
    bool rAns = checkLR(rootNode->rChild, height);
    int rHeight = height;
    height = max(lHeight, rHeight) + 1;
    if (lAns == true && rAns == true && abs(lHeight - rHeight) <= 1) {
        return true;
    } else {
        return false;
    }
}
bool checkBalanceBTree(BNode *rootNode) {
    int height = 0;
    return checkLR(rootNode, height);
}

參考文章

二叉樹-你必須要懂属划！