深入淺出！二叉樹詳解，還包含C代碼

1. 前序遍歷，中序遍歷，后序遍歷；
2. 層次遍歷；
3. 求樹的結(jié)點(diǎn)數(shù)；
4. 求樹的葉子數(shù)；
5. 求樹的深度；
6. 求二叉樹第k層的結(jié)點(diǎn)個(gè)數(shù)；
7. 判斷兩棵二叉樹是否結(jié)構(gòu)相同；
8. 求二叉樹的鏡像；
9. 求兩個(gè)結(jié)點(diǎn)的最低公共祖先結(jié)點(diǎn)；
10. 求任意兩結(jié)點(diǎn)距離；
11. 找出二叉樹中某個(gè)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)；
12. 不使用遞歸和棧遍歷二叉樹；
13. 二叉樹前序中序推后序；
14. 判斷二叉樹是不是完全二叉樹；
15. 判斷是否是二叉查找樹的后序遍歷結(jié)果；
16. 給定一個(gè)二叉查找樹中的結(jié)點(diǎn)，找出在中序遍歷下它的后繼和前驅(qū)；
17. 二分查找樹轉(zhuǎn)化為排序的循環(huán)雙鏈表；
18. 有序鏈表轉(zhuǎn)化為平衡的二分查找樹；
19. 判斷是否是二叉查找樹。

1 前序遍歷，中序遍歷，后序遍歷；

1.1 前序遍歷

對(duì)于當(dāng)前結(jié)點(diǎn)，先輸出該結(jié)點(diǎn)，然后輸出它的左孩子，最后輸出它的右孩子。以上圖為例，遞歸的過程如下：

1. 輸出 1，接著左孩子；
2. 輸出 2，接著左孩子；
3. 輸出 4，左孩子為空，再接著右孩子；
4. 輸出 6，左孩子為空，再接著右孩子；
5. 輸出 7，左右孩子都為空，此時(shí) 2 的左子樹全部輸出，2 的右子樹為空，此時(shí) 1 的左子樹全部輸出，接著 1 的右子樹；
6. 輸出 3，接著左孩子；
7. 輸出 5，左右孩子為空，此時(shí) 3 的左子樹全部輸出，3 的右子樹為空，至此 1 的右子樹全部輸出，結(jié)束。

而非遞歸版本只是利用 stack 模擬上述過程而已，遞歸的過程也就是出入棧的過程。

/* 前序遍歷遞歸版 */
void PreOrderRec(Node * node)
{
    if (node == nullptr)
        return;
    cout << node->data << " ";   // 先輸出當(dāng)前結(jié)點(diǎn)   
    PreOrderRec(node->left);     // 然后輸出左孩子
    PreOrderRec(node->right);    // 最后輸出右孩子
}

/* 前序遍歷非遞歸版 */
void PreOrderNonRec(Node * node)
{
    if (node == nullptr)
        return;

    stack<Node*> S;
    cout << node->data << " ";
    S.push(node);
    node = node->left;

    while (!S.empty() || node)
    {
        while (node)
        {
            cout << node->data << " "; // 先輸出當(dāng)前結(jié)點(diǎn)  
            S.push(node);
            node = node->left;         // 然后輸出左孩子
        }                              // while 結(jié)束意味著左孩子已經(jīng)全部輸出

        node = S.top()->right;         // 最后輸出右孩子
        S.pop();
    }
}

1.2 中序遍歷

對(duì)于當(dāng)前結(jié)點(diǎn)，先輸出它的左孩子，然后輸出該結(jié)點(diǎn)，最后輸出它的右孩子。以（1.1）圖為例：

1. 1-->2-->4，4 的左孩子為空，輸出 4，接著右孩子；
2. 6 的左孩子為空，輸出 6，接著右孩子；
3. 7 的左孩子為空，輸出 7，右孩子也為空，此時(shí) 2 的左子樹全部輸出，輸出 2，2 的右孩子為空，此時(shí) 1 的左子樹全部輸出，輸出 1，接著 1 的右孩子；
4. 3-->5，5 左孩子為空，輸出 5，右孩子也為空，此時(shí) 3 的左子樹全部輸出，而 3 的右孩子為空，至此 1 的右子樹全部輸出，結(jié)束。

/* 中序遍歷遞歸版 */
void InOrderRec(Node * node)
{
    if (node == nullptr)
        return;

    InOrderRec(node->left);     // 先輸出左孩子
    cout << node->data << " ";  // 然后輸出當(dāng)前結(jié)點(diǎn)
    InOrderRec(node->right);    // 最后輸出右孩子
}

/* 前序遍歷非遞歸版 */
void InOrderNonRec(Node * node)
{
    if (node == nullptr)
        return;

    stack<Node*> S;
    S.push(node);
    node = node->left;

    while (!S.empty() || node)
    {
        while (node)
        {
            S.push(node);
            node = node->left;
        }                             // while 結(jié)束意味著左孩子為空

        cout << S.top()->data << " "; // 左孩子已經(jīng)全部輸出，接著輸出當(dāng)前結(jié)點(diǎn)
        node = S.top()->right;        // 左孩子全部輸出，當(dāng)前結(jié)點(diǎn)也輸出后，最后輸出右孩子
        S.pop();
    }
}

1.3 后序遍歷

對(duì)于當(dāng)前結(jié)點(diǎn)，先輸出它的左孩子，然后輸出它的右孩子，最后輸出該結(jié)點(diǎn)。依舊以（1.1）圖為例：

1. 1->2->4->6->7，7 無(wú)左孩子，也無(wú)右孩子，輸出 7，此時(shí) 6 無(wú)左孩子，而 6 的右子樹也全部輸出，輸出 6，此時(shí) 4 無(wú)左子樹，而 4 的右子樹已全部輸出，接著輸出 4，此時(shí) 2 的左子樹全部輸出，且 2 無(wú)右子樹，輸出 2，此時(shí) 1 的左子樹全部輸出，接著轉(zhuǎn)向右子樹；
2. 3->5，5 無(wú)左孩子，也無(wú)右孩子，輸出 5，此時(shí) 3 的左子樹全部輸出，且 3 無(wú)右孩子，輸出 3，此時(shí) 1 的右子樹全部輸出，輸出 1，結(jié)束。

非遞歸版本中，對(duì)于一個(gè)結(jié)點(diǎn)，如果我們要輸出它，只有它既沒有左孩子也沒有右孩子或者它有孩子但是它的孩子已經(jīng)被輸出（由此設(shè)置 pre 變量）。若非上述兩種情況，則將該結(jié)點(diǎn)的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時(shí)候,先依次遍歷左子樹和右子樹。

/* 后序遍歷遞歸版 */
void PostOrderRec(Node * node)
{
    if (node == nullptr)
        return;

    PostOrderRec(node->left);   // 先輸出左孩子
    PostOrderRec(node->right);  // 然后輸出右孩子
    cout << node->data << " ";  // 最后輸出當(dāng)前結(jié)點(diǎn)
}

/* 后序遍歷非遞歸版 */
void PostOrderNonRec(Node * node)
{
    if (node == nullptr)
        return;

    Node * pre = nullptr;
    stack<Node*> S;
    S.push(node);

    while (!S.empty())
    {
        node = S.top();

        if ((!node->left && !node->right) ||                    // 第一個(gè)輸出的必是無(wú)左右孩子的葉子結(jié)點(diǎn)，只要第一個(gè)結(jié)點(diǎn)輸出，
            (pre && (pre == node->left || pre == node->right))) // 以后的 pre 就不會(huì)是空。此處的判斷語(yǔ)句加入一個(gè) pre，只是用來(lái)
        {                                                       // 確?？梢哉_輸出第一個(gè)結(jié)點(diǎn)。
            cout << node->data << " ";  // 左右孩子都全部輸出，再輸出當(dāng)前結(jié)點(diǎn)
            pre = node;
            S.pop();
        }
        else
        {
            if (node->right)
                S.push(node->right);  // 先進(jìn)右孩子，再進(jìn)左孩子，取出來(lái)的才是左孩子
            if (node->left)
                S.push(node->left);
        }
    }
}

2 層次遍歷

void LevelOrder(Node * node)
{
    Node * p = node;
    queue<Node*> Q;  // 隊(duì)列
    Q.push(p);

    while (!Q.empty())
    {
        p = Q.front();
        cout << p->data << " ";
        Q.pop();

        if (p->left)
            Q.push(p->left);  // 注意順序，先進(jìn)左孩子
        if (p->right)
            Q.push(p->right);
    }
}

3 求樹的結(jié)點(diǎn)數(shù)

int CountNodes(Node * node)
{
    if (node == nullptr)
        return 0;

    return CountNodes(node->left) + CountNodes(node->right) + 1;
}

4 求樹的葉子數(shù)

int CountLeaves(Node * node)
{
    if (node == nullptr)
        return 0;

    if (!node->left && !node->right)
        return 1;

    return CountLeaves(node->left) + CountLeaves(node->right);
}

5 求樹的深度

int GetDepth(Node * node)
{
    if (node == nullptr)
        return 0;

    int left_depth = GetDepth(node->left) + 1;
    int right_depth = GetDepth(node->right) + 1;

    return left_depth > right_depth ? left_depth : right_depth;
}

6 求二叉樹第k層的結(jié)點(diǎn)個(gè)數(shù)

int GetKLevel(Node * node, int k)
{
    if (node == nullptr)
        return 0;

    if (k == 1)
        return 1;

    return GetKLevel(node->left, k - 1) + GetKLevel(node->right, k - 1);
}

7 判斷兩棵二叉樹是否結(jié)構(gòu)相同

不考慮數(shù)據(jù)內(nèi)容。結(jié)構(gòu)相同意味著對(duì)應(yīng)的左子樹和對(duì)應(yīng)的右子樹都結(jié)構(gòu)相同。

bool StructureCmp(Node * node1, Node * node2)
{
    if (node1 == nullptr && node2 == nullptr)
        return true;
    else if (node1 == nullptr || node2 == nullptr)
        return false;

    return StructureCmp(node1->left, node2->left) && Str1uctureCmp(node1->right, node2->right);
}

8 求二叉樹的鏡像

對(duì)于每個(gè)結(jié)點(diǎn)，我們交換它的左右孩子即可。

void Mirror(Node * node)
{
    if (node == nullptr)
        return;

    Node * temp = node->left;
    node->left = node->right;
    node->right = temp;

    Mirror(node->left);
    Mirror(node->right);
}

9 求兩個(gè)結(jié)點(diǎn)的最低公共祖先結(jié)點(diǎn)

最低公共祖先，即 LCA（Lowest Common Ancestor），見下圖：結(jié)點(diǎn) 3 和結(jié)點(diǎn) 4 的最近公共祖先是結(jié)點(diǎn) 2，即 LCA(3,4)=2。在此，需要注意到當(dāng)兩個(gè)結(jié)點(diǎn)在同一棵子樹上的情況，如結(jié)點(diǎn) 3 和結(jié)點(diǎn) 2 的最近公共祖先為 2，即 LCA(3,2)=2。同理 LCA(5,6)=4，LCA(6,10)=1。

Node * FindLCA(Node * node, Node * target1, Node * target2)
{
    if (node == nullptr)
        return nullptr;
    if (node == target1 || node == target2)
        return node;

    Node * left = FindLCA(node->left, target1, target2);
    Node * right = FindLCA(node->right, target1, target2);
    if (left && right)  // 分別在左右子樹
        return node;

    return left ? left : right;  // 都在左子樹或右子樹
}

10 求任意兩結(jié)點(diǎn)距離

首先找到兩個(gè)結(jié)點(diǎn)的 LCA，然后分別計(jì)算 LCA 與它們的距離，最后相加即可。

int FindLevel(Node * node, Node * target)
{
    if (node == nullptr)
        return -1;
    if (node == target)
        return 0;

    int level = FindLevel(node->left, target);  // 先在左子樹找
    if (level == -1)
        level = FindLevel(node->right, target);  // 如果左子樹沒找到，在右子樹找

    if (level != -1)  // 找到了，回溯
        return level + 1;

    return -1;  // 如果左右子樹都沒找到
}

int DistanceNodes(Node * node, Node * target1, Node * target2)
{
    Node * lca = FindLCA(node, target1, target2);  // 找到最低公共祖先結(jié)點(diǎn)
    int level1 = FindLevel(lca, target1); 
    int level2 = FindLevel(lca, target2);

    return level1 + level2;
}

11 找出二叉樹中某個(gè)結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)

如果給定結(jié)點(diǎn) 5，則其所有祖先結(jié)點(diǎn)為 4,2,1。

bool FindAllAncestors(Node * node, Node * target)
{
    if (node == nullptr)
        return false;
    if (node == target)
        return true;

    if (FindAllAncestors(node->left, target) || FindAllAncestors(node->right, target))  // 找到了
    {
        cout << node->data << " ";
        return true;  // 回溯
    }

    return false;  // 如果左右子樹都沒找到
}

12 不使用遞歸和棧遍歷二叉樹

1968 年，高德納（Donald Knuth）提出一個(gè)問題：是否存在一個(gè)算法，它不使用棧也不破壞二叉樹結(jié)構(gòu)，但是可以完成對(duì)二叉樹的遍歷？隨后 1979 年，James H. Morris 提出了二叉樹線索化，解決了這個(gè)問題。（根據(jù)這個(gè)概念我們又提出了一個(gè)新的數(shù)據(jù)結(jié)構(gòu)，即線索二叉樹，因線索二叉樹不是本文要介紹的內(nèi)容，所以有興趣的朋友請(qǐng)移步線索二叉樹）

前序，中序，后序遍歷，不管是遞歸版本還是非遞歸版本，都用到了一個(gè)數(shù)據(jù)結(jié)構(gòu)--棧，為何要用棧？那是因?yàn)槠渌姆绞經(jīng)]法記錄當(dāng)前結(jié)點(diǎn)的 parent,而如果在每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)里面加個(gè) parent 分量顯然是不現(xiàn)實(shí)的，而線索化正好解決了這個(gè)問題，其含義就是利用結(jié)點(diǎn)的右孩子空指針，指向該結(jié)點(diǎn)在中序序列中的后繼。下面具體來(lái)看看如何使用線索化來(lái)完成對(duì)二叉樹的遍歷。先看前序遍歷，步驟如下：

1. 如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則輸出當(dāng)前結(jié)點(diǎn)并將其右孩子作為當(dāng)前結(jié)點(diǎn)；
2. 如果當(dāng)前結(jié)點(diǎn)的左孩子不為空，在當(dāng)前結(jié)點(diǎn)的左子樹中找到當(dāng)前結(jié)點(diǎn)在中序遍歷下的前驅(qū)結(jié)點(diǎn)；

• 2.1如果前驅(qū)結(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，輸出當(dāng)前結(jié)點(diǎn)并把當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的左孩子；
• 2.2如果前驅(qū)結(jié)點(diǎn)的右孩子為當(dāng)前結(jié)點(diǎn)，將它的右孩子重新設(shè)為空，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子；

3. 重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點(diǎn)為空。

/* 前序遍歷 */
void PreOrderMorris(Node * root)
{
    Node * cur = root;
    Node * pre = nullptr;

    while (cur)
    {
        if (cur->left == nullptr)  // 步驟 1
        {
            cout << cur->data << " ";
            cur = cur->right;
        }
        else
        {
            pre = cur->left;
            while (pre->right && pre->right != cur)  // 步驟 2，找到 cur 的前驅(qū)結(jié)點(diǎn)
                pre = pre->right;

            if (pre->right == nullptr)  // 步驟 2.1，cur 未被訪問，將 cur 結(jié)點(diǎn)作為其前驅(qū)結(jié)點(diǎn)的右孩子
            {
                cout << cur->data << " ";
                pre->right = cur;
                cur = cur->left;
            }
            else  // 步驟 2.2，cur 已被訪問，恢復(fù)樹的原有結(jié)構(gòu)，更改 right 指針 
            {
                pre->right = nullptr;
                cur = cur->right;
            }
        }
    }
}

再來(lái)看中序遍歷，和前序遍歷相比只改動(dòng)一句代碼，步驟如下：

1. 如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則輸出當(dāng)前結(jié)點(diǎn)并將其右孩子作為當(dāng)前結(jié)點(diǎn)；
2. 如果當(dāng)前結(jié)點(diǎn)的左孩子不為空，在當(dāng)前結(jié)點(diǎn)的左子樹中找到當(dāng)前結(jié)點(diǎn)在中序遍歷下的前驅(qū)結(jié)點(diǎn)；

• 2.1. 如果前驅(qū)結(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的左孩子；
• 2.2. 如果前驅(qū)結(jié)點(diǎn)的右孩子為當(dāng)前結(jié)點(diǎn)，將它的右孩子重新設(shè)為空，輸出當(dāng)前結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子；

3. 重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點(diǎn)為空。

/* 中序遍歷 */
void InOrderMorris(Node * root)
{
    Node * cur = root;
    Node * pre = nullptr;

    while (cur)
    {
        if (cur->left == nullptr)  //（1）
        {
            cout << cur->data << " ";
            cur = cur->right;
        }
        else
        {
            pre = cur->left;
            while (pre->right && pre->right != cur)  //（2），找到 cur 的前驅(qū)結(jié)點(diǎn)
                pre = pre->right;

            if (pre->right == nullptr)  //（2.1），cur 未被訪問，將 cur 結(jié)點(diǎn)作為其前驅(qū)結(jié)點(diǎn)的右孩子
            {
                pre->right = cur;
                cur = cur->left;
            }
            else  //（2.2），cur 已被訪問，恢復(fù)樹的原有結(jié)構(gòu)，更改 right 指針 
            {
                cout << cur->data << " ";
                pre->right = nullptr;
                cur = cur->right;
            }
        }
    }
}

最后看下后序遍歷，后序遍歷有點(diǎn)復(fù)雜，需要建立一個(gè)虛假根結(jié)點(diǎn) dummy，令其左孩子是 root。并且還需要一個(gè)子過程，就是倒序輸出某兩個(gè)結(jié)點(diǎn)之間路徑上的各個(gè)結(jié)點(diǎn)。步驟如下：

1. 如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則將其右孩子作為當(dāng)前結(jié)點(diǎn)；
2. 如果當(dāng)前結(jié)點(diǎn)的左孩子不為空，在當(dāng)前結(jié)點(diǎn)的左子樹中找到當(dāng)前結(jié)點(diǎn)在中序遍歷下的前驅(qū)結(jié)點(diǎn)；

• 2.1. 如果前驅(qū)結(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的左孩子；
• 2.2. 如果前驅(qū)結(jié)點(diǎn)的右孩子為當(dāng)前結(jié)點(diǎn)，將它的右孩子重新設(shè)為空，倒序輸出從當(dāng)前結(jié)點(diǎn)的左孩子到該前驅(qū)結(jié)點(diǎn)這條路徑上的所有結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子；

3. 重復(fù)以上步驟 1 和 2，直到當(dāng)前結(jié)點(diǎn)為空。

struct Node
{
    int data;
    Node * left;
    Node * right;
    Node(int  data_, Node * left_, Node * right_)
    {
        data = data_;
        left = left_;
        right = right_;
    }
};

void ReversePrint(Node * from, Node * to)
{
    if (from == to)
    {
        cout << from->data << " ";
        return;
    }
    ReversePrint(from->right, to);
    cout << from->data << " ";
}

void  PostOrderMorris(Node * root)
{
    Node * dummy = new Node(-1, root, nullptr);  // 一個(gè)虛假根結(jié)點(diǎn)
    Node * cur = dummy;
    Node * pre = nullptr;

    while (cur)
    {
        if (cur->left == nullptr)  // 步驟 1
            cur = cur->right;
        else
        {
            pre = cur->left;
            while (pre->right && pre->right != cur)  // 步驟 2，找到 cur 的前驅(qū)結(jié)點(diǎn)
                pre = pre->right;

            if (pre->right == nullptr)  // 步驟 2.1，cur 未被訪問，將 cur 結(jié)點(diǎn)作為其前驅(qū)結(jié)點(diǎn)的右孩子
            {
                pre->right = cur;
                cur = cur->left;
            }
            else  // 步驟 2.2，cur 已被訪問，恢復(fù)樹的原有結(jié)構(gòu)，更改 right 指針
            {
                pre->right = nullptr;
                ReversePrint(cur->left, pre);
                cur = cur->right;
            }
        }
    }
}

dummy 用的非常巧妙，建議讀者配合上面的圖模擬下算法流程。

13 二叉樹前序中序推后序

以上面圖表為例，步驟如下：

1. 根據(jù)前序可知根結(jié)點(diǎn)為1；
2. 根據(jù)中序可知 4 7 2 為根結(jié)點(diǎn) 1 的左子樹和 8 5 9 3 6 為根結(jié)點(diǎn) 1 的右子樹；
3. 遞歸實(shí)現(xiàn)，把 4 7 2 當(dāng)做新的一棵樹和 8 5 9 3 6 也當(dāng)做新的一棵樹；
4. 在遞歸的過程中輸出后序。

/* 前序遍歷和中序遍歷結(jié)果以長(zhǎng)度為 n 的數(shù)組存儲(chǔ)，pos1 為前序數(shù)組下標(biāo)，pos2 為后序下標(biāo) */

int pre_order_arry[n];
int in_order_arry[n];

void PrintPostOrder(int pos1, int pos2, int n)
{
    if (n == 1)
    {
        cout << pre_order_arry[pos1];
        return;
    }
    if (n == 0)
        return;

    int i = 0;
    for (; pre_order_arry[pos1] != in_order_arry[pos2 + i]; i++)
        ;

    PrintPostOrder(pos1 + 1, pos2, i);
    PrintPostOrder(pos1 + i + 1, pos2 + i + 1, n - i - 1);
    cout << pre_order_arry[pos1];
}

當(dāng)然我們也可以根據(jù)前序和中序構(gòu)造出二叉樹，進(jìn)而求出后序。

/* 該函數(shù)返回二叉樹的根結(jié)點(diǎn) */
Node * Create(int pos1, int pos2, int n)
{
    Node * p = nullptr;

    for (int i = 0; i < n; i++)
    {
        if (pre_order_arry[pos1] == in_order_arry[pos2 + i])
        {
            p = new Node(pre_order_arry[pos1]);
            p->left = Create(pos1 + 1, pos2, i);
            p->right = Create(pos1 + i + 1, pos2 + i + 1, n - i - 1);
            return p;
        }
    }

    return p;
}

14 判斷二叉樹是不是完全二叉樹

若設(shè)二叉樹的深度為 h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹（Complete Binary Tree）。如下圖：

首先若一個(gè)結(jié)點(diǎn)只有右孩子，肯定不是完全二叉樹；其次若只有左孩子或沒有孩子，那么接下來(lái)的所有結(jié)點(diǎn)肯定都沒有孩子，否則就不是完全二叉樹，因此設(shè)置 flag 標(biāo)記變量。

bool IsCBT(Node * node)
{
    bool flag = false;
    queue<Node*> Q;
    Q.push(node);

    while (!Q.empty())
    {
        Node * p = Q.front();
        Q.pop();

        if (flag)
        {
            if (p->left || p->right)
                return false;
        }
        else
        {
            if (p->left && p->right)
            {
                Q.push(p->left);
                Q.push(p->right);
            }
            else if (p->right)  // 只有右結(jié)點(diǎn)
                return false;
            else if (p->left)   // 只有左結(jié)點(diǎn)
            {
                Q.push(p->left);
                flag = true;
            }
            else  // 沒有結(jié)點(diǎn)
                flag = true;
        }
    }

    return true;
}

15 判斷是否是二叉查找樹的后序遍歷結(jié)果

在后續(xù)遍歷得到的序列中，最后一個(gè)元素為樹的根結(jié)點(diǎn)。從頭開始掃描這個(gè)序列，比根結(jié)點(diǎn)小的元素都應(yīng)該位于序列的左半部分；從第一個(gè)大于跟結(jié)點(diǎn)開始到跟結(jié)點(diǎn)前面的一個(gè)元素為止，所有元素都應(yīng)該大于跟結(jié)點(diǎn)，因?yàn)檫@部分元素對(duì)應(yīng)的是樹的右子樹。根據(jù)這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認(rèn)序列的左、右兩部分是不是都是二元查找樹。

int array[n];  // 長(zhǎng)度為 n 的序列，注意 begin 和 end 遵循的是左閉右閉原則

bool IsSequenceOfBST(int begin, int end)
{
    if (end - begin <= 0)
        return true;

    int root_data = array[end];  // 數(shù)組尾元素為根結(jié)點(diǎn)

    int i = begin;
    for (; array[i] < root_data; i++) // 取得左子樹
        ;

    int j = i;
    for (; j < end; j++)
        if (array[j] < root_data)  // 此時(shí)右子樹應(yīng)該都大于根結(jié)點(diǎn)；若存在小于，直接 return false
            return false;

    return IsSequenceOfBST(begin, i - 1) && IsSequenceOfBST(i, end - 1);  // 左右子樹是否都滿足
}

16 給定一個(gè)二叉查找樹中的結(jié)點(diǎn)（存在一個(gè)指向父親結(jié)點(diǎn)的指針），找出在中序遍歷下它的后繼和前驅(qū)

一棵二叉查找樹的中序遍歷序列，正好是升序序列。假如根結(jié)點(diǎn)的父結(jié)點(diǎn)為 nullptr，則：

1. 如果當(dāng)前結(jié)點(diǎn)有右孩子，則后繼結(jié)點(diǎn)為這個(gè)右孩子的最左孩子；
2. 如果當(dāng)前結(jié)點(diǎn)沒有右孩子；

• 2.1. 當(dāng)前結(jié)點(diǎn)為根結(jié)點(diǎn)，返回 nullptr；
• 2.2. 當(dāng)前結(jié)點(diǎn)只是個(gè)普通結(jié)點(diǎn)，也就是存在父結(jié)點(diǎn)；
• 2.2.1. 當(dāng)前結(jié)點(diǎn)是父親結(jié)點(diǎn)的左孩子，則父親結(jié)點(diǎn)就是后繼結(jié)點(diǎn)；
• 2.2.2. 當(dāng)前結(jié)點(diǎn)是父親結(jié)點(diǎn)的右孩子，沿著父親結(jié)點(diǎn)往上走，直到 n-1 代祖先是 n 代祖先的左孩子，則后繼為 n 代祖先或遍歷到根結(jié)點(diǎn)也沒找到符合的，則當(dāng)前結(jié)點(diǎn)就是中序遍歷的最后一個(gè)結(jié)點(diǎn)，返回 nullptr。

/* 求后繼結(jié)點(diǎn) */
Node * Increment(Node * node)
{
    if (node->right)  // 步驟 1
    {
        node = node->right;
        while (node->left)
            node = node->left;
        return node;
    }
    else  // 步驟 2
    {
        if (node->parent == nullptr)  // 步驟 2.1
            return nullptr;
        Node * p = node->parent;  // 步驟 2.2
        if (p->left == node)  // 步驟 2.2.1
            return p;
        else  // 步驟 2.2.2
        {
            while (p->right == node)
            {
                node = p;
                p = p->parent;
                if (p == nullptr)
                    return nullptr;
            }
            return p;
        }
    }
}

仔細(xì)觀察上述代碼，總覺得有點(diǎn)啰嗦。比如，過多的 return，步驟 2 的層次太多。綜合考慮所有情況，改進(jìn)代碼如下：

Node * Increment(Node * node)
{
    if (node->right)
    {
        node = node->right;
        while (node->left)
            node = node->left;
    }
    else
    {
        Node * p = node->parent;
        while (p && p->right == node)
        {
            node = p;
            p = p->parent;
        }
        node = p;
    }

    return node;
}

上述的代碼是基于結(jié)點(diǎn)有 parent 指針的，若題意要求沒有 parent 呢？網(wǎng)上也有人給出了答案，個(gè)人覺得沒有什么價(jià)值，有興趣的朋友可以到這里查看。

而求前驅(qū)結(jié)點(diǎn)的話，只需把上述代碼的 left 與 right 互調(diào)即可，很簡(jiǎn)單。

17 二分查找樹轉(zhuǎn)化為排序的循環(huán)雙鏈表

二分查找樹的中序遍歷即為升序排列，問題就在于如何在遍歷的時(shí)候更改指針的指向。一種簡(jiǎn)單的方法時(shí)，遍歷二分查找樹，將遍歷的結(jié)果放在一個(gè)數(shù)組中，之后再把該數(shù)組轉(zhuǎn)化為雙鏈表。如果題目要求只能使用 O(1)O(1) 內(nèi)存，則只能在遍歷的同時(shí)構(gòu)建雙鏈表，即進(jìn)行指針的替換。

我們需要用遞歸的方法來(lái)解決，假定每個(gè)遞歸調(diào)用都會(huì)返回構(gòu)建好的雙鏈表，可把問題分解為左右兩個(gè)子樹。由于左右子樹都已經(jīng)是有序的，當(dāng)前結(jié)點(diǎn)作為中間的一個(gè)結(jié)點(diǎn)，把左右子樹得到的鏈表連接起來(lái)即可。

/* 合并兩個(gè) a, b 兩個(gè)循環(huán)雙向鏈表 */
Node * Append(Node * a, Node * b)
{
    if (a == nullptr) return b;
    if (b == nullptr) return a;

    // 分別得到兩個(gè)鏈表的最后一個(gè)元素
    Node * a_last = a->left;
    Node * b_last = b->left;

    // 將兩個(gè)鏈表頭尾相連  
    a_last->right = b;
    b->left = a_last;

    a->left = b_last;
    b_last->right = a;

    return a;
}

/* 遞歸的解決二叉樹轉(zhuǎn)換為雙鏈表 */
Node * TreeToList(Node * node)
{
    if (node == nullptr) return nullptr;

    // 遞歸解決子樹
    Node * left_list = TreeToList(node->left);
    Node * right_list = TreeToList(node->right);

    // 把根結(jié)點(diǎn)轉(zhuǎn)換為一個(gè)結(jié)點(diǎn)的雙鏈表，方便后面的鏈表合并  
    node->left = node;
    node->right = node;

    // 合并之后即為升序排列
    left_list = Append(left_list, node);
    left_list = Append(left_list, right_list);

    return left_list;
}

18 有序鏈表轉(zhuǎn)化為平衡的二分查找樹（Binary Search Tree）

我們可以采用自頂向下的方法。先找到中間結(jié)點(diǎn)作為根結(jié)點(diǎn)，然后遞歸左右兩部分。所以我們需要先找到中間結(jié)點(diǎn)，對(duì)于單鏈表來(lái)說(shuō)，必須要遍歷一邊，可以使用快慢指針加快查找速度。

struct TreeNode
{
    int data;
    TreeNode * left;
    TreeNode * right;
    TreeNode(int data_) { data = data_; left = right = nullptr; }
};

struct ListNode
{
    int data;
    ListNode * next;
    ListNode(int data_) { data = data_; next = nullptr; }
};

TreeNode * SortedListToBST(ListNode *  list_node)
{
    if (!list_node) return nullptr;
    if (!list_node->next) return (new TreeNode(list_node->data));

    // 用快慢指針找到中間結(jié)點(diǎn)  
    ListNode * pre_slow = nullptr;  // 記錄慢指針的前一個(gè)結(jié)點(diǎn)
    ListNode * slow = list_node;    // 慢指針
    ListNode * fast = list_node;    // 快指針
    while (fast && fast->next)
    {
        pre_slow = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    TreeNode * mid = new TreeNode(slow->data);

    // 分別遞歸左右兩部分
    if (pre_slow)
    {
        pre_slow->next = nullptr;
        mid->left = SortedListToBST(list_node);
    }
    mid->right = SortedListToBST(slow->next);

    return mid;
}

由 f(n)=2f(\frac n2)+\frac n2f(n)=2f(2n)+2n 得，所以上述算法的時(shí)間復(fù)雜度為 O(nlogn)O(nlogn)。

不妨換個(gè)思路，采用自底向上的方法：

TreeNode * SortedListToBSTRec(ListNode *& list, int start, int end)
{
    if (start > end) return nullptr;

    int mid = start + (end - start) / 2;
    TreeNode * left_child = SortedListToBSTRec(list, start, mid - 1);  // 注意此處傳入的是引用
    TreeNode * parent = new TreeNode(list->data);
    parent->left = left_child;
    list = list->next;
    parent->right = SortedListToBSTRec(list, mid + 1, end);
    return parent;
}

TreeNode * SortedListToBST(ListNode * node)
{
    int n = 0;
    ListNode * p = node;
    while (p)
    {
        n++;
        p = p->next;
    }

    return SortedListToBSTRec(node, 0, n - 1);
}

如此，時(shí)間復(fù)雜度降為 O(n)O(n)。

19 判斷是否是二叉查找樹

我們假定二叉樹沒有重復(fù)元素，即對(duì)于每個(gè)結(jié)點(diǎn)，其左右孩子都是嚴(yán)格的小于和大于。

下面給出兩個(gè)方法：

方法 1：

bool IsBST(Node * node, int min, int max)
{
    if (node == nullptr)
        return true;
    if (node->data <= min || node->data >= max)
        return false;

    return IsBST(node->left, min, node->data) && IsBST(node->right, node->data, max);
}

IsBST(node, INT_MIN, INT_MAX);

方法 2：

利用二叉查找樹中序遍歷時(shí)元素遞增來(lái)判斷。

bool IsBST(Node * node)
{
    static int pre = INT_MIN;

    if (node == nullptr)
        return true;

    if (!IsBST(node->left))
        return false;

    if (node->data < pre)
        return false;
    pre = node->data;

    return IsBST(node->right);
}