數據結構面試之二叉樹相關操作

在數據結構面試環節中，二叉樹是必考的模塊。本文主要講二叉樹操作的相關知識，梳理面試常考的內容。一起來復習吧。本篇針對面試中常見的二叉樹操作作個總結：

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

層次遍歷；

求樹的結點數；

求樹的葉子數；

求樹的深度；

求二叉樹第k層的結點個數；

判斷兩棵二叉樹是否結構相同；

求二叉樹的鏡像；

求兩個結點的最低公共祖先結點；

求任意兩結點距離；

找出二叉樹中某個結點的所有祖先結點；

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

二叉樹前序中序推后序；

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

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

給定一個二叉查找樹中的結點，找出在中序遍歷下它的后繼和前驅；

二分查找樹轉化為排序的循環雙鏈表；

有序鏈表轉化為平衡的二分查找樹；

判斷是否是二叉查找樹。

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

1.1 前序遍歷

對于當前結點，先輸出該結點，然后輸出它的左孩子，最后輸出它的右孩子。以上圖為例，遞歸的過程如下：

輸出 1，接著左孩子；

輸出 2，接著左孩子；

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

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

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

輸出 3，接著左孩子；

輸出 5，左右孩子為空，此時 3 的左子樹全部輸出，3 的右子樹為空，至此 1 的右子樹全部輸出，結束。

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

/* 前序遍歷遞歸版 */
void PreOrderRec(Node * node)
{
    if (node == nullptr)
        return;
    cout << node->data << " ";   // 先輸出當前結點   
    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 << " "; // 先輸出當前結點  
            S.push(node);
            node = node->left;     // 然后輸出左孩子
        }                           // while 結束意味著左孩子已經全部輸出


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

1.2 中序遍歷

對于當前結點，先輸出它的左孩子，然后輸出該結點，最后輸出它的右孩子。以（1.1）圖為例：

1-->2-->4，4 的左孩子為空，輸出 4，接著右孩子；

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

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

3-->5，5 左孩子為空，輸出 5，右孩子也為空，此時 3 的左子樹全部輸出，而 3 的右孩子為空，至此 1 的右子樹全部輸出，結束。

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


    InOrderRec(node->left);     // 先輸出左孩子
    cout << node->data << " ";  // 然后輸出當前結點
    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 結束意味著左孩子為空


        cout << S.top()->data << " "; // 左孩子已經全部輸出，接著輸出當前結點
        node = S.top()->right;        // 左孩子全部輸出，當前結點也輸出后，最后輸出右孩子
        S.pop();
    }
}

1.3 后序遍歷

對于當前結點，先輸出它的左孩子，然后輸出它的右孩子，最后輸出該結點。依舊以（1.1）圖為例：

1->2->4->6->7，7 無左孩子，也無右孩子，輸出 7，此時 6 無左孩子，而 6 的右子樹也全部輸出，輸出 6，此時 4 無左子樹，而 4 的右子樹已全部輸出，接著輸出 4，此時 2 的左子樹全部輸出，且 2 無右子樹，輸出 2，此時 1 的左子樹全部輸出，接著轉向右子樹；

3->5，5 無左孩子，也無右孩子，輸出 5，此時 3 的左子樹全部輸出，且 3 無右孩子，輸出 3，此時 1 的右子樹全部輸出，輸出 1，結束。

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

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


    PostOrderRec(node->left);   // 先輸出左孩子
    PostOrderRec(node->right);  // 然后輸出右孩子
    cout << node->data << " ";  // 最后輸出當前結點
}


/* 后序遍歷非遞歸版 */
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) ||                    // 第一個輸出的必是無左右孩子的葉子結點，只要第一個結點輸出，
            (pre && (pre == node->left || pre == node->right))) // 以后的 pre 就不會是空。此處的判斷語句加入一個 pre，只是用來
        {                                                       // 確?？梢哉_輸出第一個結點。
            cout << node->data << " ";  // 左右孩子都全部輸出，再輸出當前結點
            pre = node;
            S.pop();
        }
        else
        {
            if (node->right)
                S.push(node->right);  // 先進右孩子，再進左孩子，取出來的才是左孩子
            if (node->left)
                S.push(node->left);
        }
    }
}

2 層次遍歷

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


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


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

?3 求樹的結點數

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


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

?4 求樹的葉子數

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層的結點個數

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 判斷兩棵二叉樹是否結構相同

不考慮數據內容。結構相同意味著對應的左子樹和對應的右子樹都結構相同。

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 求二叉樹的鏡像

對于每個結點，我們交換它的左右孩子即可。

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 求兩個結點的最低公共祖先結點

最低公共祖先，即 LCA（Lowest Common Ancestor），見下圖：

結點 3 和結點 4 的最近公共祖先是結點 2，即 LCA(3,4)=2。在此，需要注意到當兩個結點在同一棵子樹上的情況，如結點 3 和結點 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 求任意兩結點距離

首先找到兩個結點的 LCA，然后分別計算 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);  // 找到最低公共祖先結點
    int level1 = FindLevel(lca, target1); 
    int level2 = FindLevel(lca, target2);


    return level1 + level2;
}

?11 找出二叉樹中某個結點的所有祖先結點

如果給定結點 5，則其所有祖先結點為 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）提出一個問題：是否存在一個算法，它不使用棧也不破壞二叉樹結構，但是可以完成對二叉樹的遍歷？隨后 1979 年，James H. Morris 提出了二叉樹線索化，解決了這個問題。（根據這個概念我們又提出了一個新的數據結構，即線索二叉樹，因線索二叉樹不是本文要介紹的內容，所以有興趣的朋友請移步線索二叉樹）前序，中序，后序遍歷，不管是遞歸版本還是非遞歸版本，都用到了一個數據結構--棧，為何要用棧？那是因為其它的方式沒法記錄當前結點的 parent,而如果在每個結點的結構里面加個 parent 分量顯然是不現實的，而線索化正好解決了這個問題，其含義就是利用結點的右孩子空指針，指向該結點在中序序列中的后繼。下面具體來看看如何使用線索化來完成對二叉樹的遍歷。

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

如果當前結點的左孩子為空，則輸出當前結點并將其右孩子作為當前結點；

如果當前結點的左孩子不為空，在當前結點的左子樹中找到當前結點在中序遍歷下的前驅結點；

2.1如果前驅結點的右孩子為空，將它的右孩子設置為當前結點，輸出當前結點并把當前結點更新為當前結點的左孩子；

2.2如果前驅結點的右孩子為當前結點，將它的右孩子重新設為空，當前結點更新為當前結點的右孩子；

重復以上步驟 1 和 2，直到當前結點為空。

/* 前序遍歷 */
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 的前驅結點
                pre = pre->right;


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

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

如果當前結點的左孩子為空，則輸出當前結點并將其右孩子作為當前結點；

如果當前結點的左孩子不為空，在當前結點的左子樹中找到當前結點在中序遍歷下的前驅結點；

2.1. 如果前驅結點的右孩子為空，將它的右孩子設置為當前結點，當前結點更新為當前結點的左孩子；

2.2. 如果前驅結點的右孩子為當前結點，將它的右孩子重新設為空，輸出當前結點，當前結點更新為當前結點的右孩子；

重復以上步驟 1 和 2，直到當前結點為空。

/* 中序遍歷 */
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 的前驅結點
                pre = pre->right;


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

? 最后看下后序遍歷，后序遍歷有點復雜，需要建立一個虛假根結點 dummy，令其左孩子是 root。并且還需要一個子過程，就是倒序輸出某兩個結點之間路徑上的各個結點。

步驟如下：

如果當前結點的左孩子為空，則將其右孩子作為當前結點；

如果當前結點的左孩子不為空，在當前結點的左子樹中找到當前結點在中序遍歷下的前驅結點；

2.1. 如果前驅結點的右孩子為空，將它的右孩子設置為當前結點，當前結點更新為當前結點的左孩子；

2.2. 如果前驅結點的右孩子為當前結點，將它的右孩子重新設為空，倒序輸出從當前結點的左孩子到該前驅結點這條路徑上的所有結點，當前結點更新為當前結點的右孩子；

重復以上步驟 1 和 2，直到當前結點為空。

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);  // 一個虛假根結點
    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 的前驅結點
                pre = pre->right;


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

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

13 二叉樹前序中序推后序

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

根據前序可知根結點為1；

根據中序可知 4 7 2 為根結點 1 的左子樹和 8 5 9 3 6 為根結點 1 的右子樹；

遞歸實現，把 4 7 2 當做新的一棵樹和 8 5 9 3 6 也當做新的一棵樹；

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

/* 前序遍歷和中序遍歷結果以長度為 n 的數組存儲，pos1 為前序數組下標，pos2 為后序下標 */


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

? 當然我們也可以根據前序和中序構造出二叉樹，進而求出后序。

/* 該函數返回二叉樹的根結點 */
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 判斷二叉樹是不是完全二叉樹

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

首先若一個結點只有右孩子，肯定不是完全二叉樹；其次若只有左孩子或沒有孩子，那么接下來的所有結點肯定都沒有孩子，否則就不是完全二叉樹，因此設置 flag 標記變量。

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)  // 只有右結點
                return false;
            else if (p->left)   // 只有左結點
            {
                Q.push(p->left);
                flag = true;
            }
            else  // 沒有結點
                flag = true;
        }
    }


    return true;
}

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

在后續遍歷得到的序列中，最后一個元素為樹的根結點。從頭開始掃描這個序列，比根結點小的元素都應該位于序列的左半部分；從第一個大于跟結點開始到跟結點前面的一個元素為止，所有元素都應該大于跟結點，因為這部分元素對應的是樹的右子樹。根據這樣的劃分，把序列劃分為左右兩部分，我們遞歸地確認序列的左、右兩部分是不是都是二元查找樹。

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


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


    int root_data = array[end];  // 數組尾元素為根結點


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


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


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

?16 給定一個二叉查找樹中的結點（存在一個指向父親結點的指針），找出在中序遍歷下它的后繼和前驅

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

如果當前結點有右孩子，則后繼結點為這個右孩子的最左孩子；

如果當前結點沒有右孩子；

2.1. 當前結點為根結點，返回 nullptr；

2.2. 當前結點只是個普通結點，也就是存在父結點；

2.2.1. 當前結點是父親結點的左孩子，則父親結點就是后繼結點；

2.2.2. 當前結點是父親結點的右孩子，沿著父親結點往上走，直到 n-1 代祖先是 n 代祖先的左孩子，則后繼為 n 代祖先或遍歷到根結點也沒找到符合的，則當前結點就是中序遍歷的最后一個結點，返回 nullptr。

/* 求后繼結點 */
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;
        }
    }
}

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

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

? 上述的代碼是基于結點有 parent 指針的，若題意要求沒有 parent 呢？網上也有人給出了答案，個人覺得沒有什么價值，有興趣的朋友可以到這里查看。而求前驅結點的話，只需把上述代碼的 left 與 right 互調即可，很簡單。

17 二分查找樹轉化為排序的循環雙鏈表

二分查找樹的中序遍歷即為升序排列，問題就在于如何在遍歷的時候更改指針的指向。一種簡單的方法時，遍歷二分查找樹，將遍歷的結果放在一個數組中，之后再把該數組轉化為雙鏈表。如果題目要求只能使用 O(1)O(1) 內存，則只能在遍歷的同時構建雙鏈表，即進行指針的替換。我們需要用遞歸的方法來解決，假定每個遞歸調用都會返回構建好的雙鏈表，可把問題分解為左右兩個子樹。由于左右子樹都已經是有序的，當前結點作為中間的一個結點，把左右子樹得到的鏈表連接起來即可。

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


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


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


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


    return a;
}


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


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


    // 把根結點轉換為一個結點的雙鏈表，方便后面的鏈表合并  
    node->left = node;
    node->right = node;


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


    return left_list;
}

?18 有序鏈表轉化為平衡的二分查找樹（Binary Search Tree）

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

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


    // 用快慢指針找到中間結點  
    ListNode * pre_slow = nullptr;  // 記錄慢指針的前一個結點
    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 得，所以上述算法的時間復雜度為 O(nlogn)O(nlogn)。不妨換個思路，采用自底向上的方法：

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

? 如此，時間復雜度降為 O(n)O(n)。

19 判斷是否是二叉查找樹

我們假定二叉樹沒有重復元素，即對于每個結點，其左右孩子都是嚴格的小于和大于。下面給出兩個方法：方法 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：利用二叉查找樹中序遍歷時元素遞增來判斷。

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

? 編輯：黃飛

閱讀全文