數(shù)據(jù)結(jié)構(gòu)面試之二叉樹相關(guān)操作

在數(shù)據(jù)結(jié)構(gòu)面試環(huán)節(jié)中，二叉樹是必考的模塊。本文主要講二叉樹操作的相關(guān)知識(shí)，梳理面試常考的內(nèi)容。一起來復(fù)習(xí)吧。本篇針對(duì)面試中常見的二叉樹操作作個(gè)總結(jié)：

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

層次遍歷；

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

求樹的葉子數(shù)；

求樹的深度；

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

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

求二叉樹的鏡像；

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

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

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

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

二叉樹前序中序推后序；

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

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

給定一個(gè)二叉查找樹中的結(jié)點(diǎn)，找出在中序遍歷下它的后繼和前驅(qū)；

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

有序鏈表轉(zhuǎn)化為平衡的二分查找樹；

判斷是否是二叉查找樹。

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

1.1 前序遍歷

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

輸出 1，接著左孩子；

輸出 2，接著左孩子；

輸出 4，左孩子為空，再接著右孩子；

輸出 6，左孩子為空，再接著右孩子；

輸出 7，左右孩子都為空，此時(shí) 2 的左子樹全部輸出，2 的右子樹為空，此時(shí) 1 的左子樹全部輸出，接著 1 的右子樹；

輸出 3，接著左孩子；

輸出 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 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-->2-->4，4 的左孩子為空，輸出 4，接著右孩子；

6 的左孩子為空，輸出 6，接著右孩子；

7 的左孩子為空，輸出 7，右孩子也為空，此時(shí) 2 的左子樹全部輸出，輸出 2，2 的右孩子為空，此時(shí) 1 的左子樹全部輸出，輸出 1，接著 1 的右孩子；

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 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->2->4->6->7，7 無左孩子，也無右孩子，輸出 7，此時(shí) 6 無左孩子，而 6 的右子樹也全部輸出，輸出 6，此時(shí) 4 無左子樹，而 4 的右子樹已全部輸出，接著輸出 4，此時(shí) 2 的左子樹全部輸出，且 2 無右子樹，輸出 2，此時(shí) 1 的左子樹全部輸出，接著轉(zhuǎn)向右子樹；

3->5，5 無左孩子，也無右孩子，輸出 5，此時(shí) 3 的左子樹全部輸出，且 3 無右孩子，輸出 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 S;
    S.push(node);


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


        if ((!node->left && !node->right) ||                    // 第一個(gè)輸出的必是無左右孩子的葉子結(jié)點(diǎn)，只要第一個(gè)結(jié)點(diǎn)輸出，
            (pre && (pre == node->left || pre == node->right))) // 以后的 pre 就不會(huì)是空。此處的判斷語句加入一個(gè) pre，只是用來
        {                                                       // 確保可以正確輸出第一個(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)左孩子，取出來的才是左孩子
            if (node->left)
                S.push(node->left);
        }
    }
}

2 層次遍歷

void LevelOrder(Node * node)
{
    Node * p = node;
    queue 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)在中序序列中的后繼。下面具體來看看如何使用線索化來完成對(duì)二叉樹的遍歷。

先看前序遍歷，步驟如下：

如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則輸出當(dāng)前結(jié)點(diǎn)并將其右孩子作為當(dāng)前結(jié)點(diǎn)；

如果當(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)的右孩子；

重復(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;
            }
        }
    }
}

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

如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則輸出當(dāng)前結(jié)點(diǎn)并將其右孩子作為當(dāng)前結(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)的右孩子；

重復(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)。

步驟如下：

如果當(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)的右孩子；

重復(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 二叉樹前序中序推后序

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

根據(jù)前序可知根結(jié)點(diǎn)為1；

根據(jù)中序可知 4 7 2 為根結(jié)點(diǎn) 1 的左子樹和 8 5 9 3 6 為根結(jié)點(diǎn) 1 的右子樹；

遞歸實(shí)現(xiàn)，把 4 7 2 當(dāng)做新的一棵樹和 8 5 9 3 6 也當(dāng)做新的一棵樹；

在遞歸的過程中輸出后序。

/* 前序遍歷和中序遍歷結(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)只有右孩子，肯定不是完全二叉樹；其次若只有左孩子或沒有孩子，那么接下來的所有結(jié)點(diǎn)肯定都沒有孩子，否則就不是完全二叉樹，因此設(shè)置 flag 標(biāo)記變量。

bool IsCBT(Node * node)
{
    bool flag = false;
    queue 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，則：

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

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

/* 合并兩個(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ì)于單鏈表來說，必須要遍歷一邊，可以使用快慢指針加快查找速度。

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í)元素遞增來判斷。

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);
}

? 編輯：黃飛

閱讀全文

評(píng)論

搜索歷史

數(shù)據(jù)結(jié)構(gòu)面試之二叉樹相關(guān)操作

評(píng)論