C++如何將二叉搜索樹轉換成雙向循環鏈表(雙指針或數組)

Posted on by

二叉搜索樹轉換成雙向循環鏈表

在這裡插入圖片描述

本文解法基於性質：二叉搜索樹的中序遍歷為 遞增序列 。

將二叉搜索樹 轉換成一個 “排序的循環雙向鏈表”，其中包含三個要素：

1.排序鏈表：節點應從小到大排序，因此應使用 中序遍歷

2.“從小到大”訪問樹的節點。雙向鏈表：在構建相鄰節點的引用關系時，設前驅節點 pre 和當前節點 cur ，

不僅應構建 pre.right= cur，也應構建 cur.left = pre 。

3.循環鏈表：設鏈表頭節點 head 和尾節點 tail，則應構建 head.left = tail 和 tail.right = head 。

雙指針：

class Solution {
private:
    Node* head, * pre = NULL;
public:
    Node* treeToDoublyList(Node* root) {//雙指針做法
        if (!root) return NULL;
        inorder(root);
        head->left = pre;
        pre->right = head;
        return head;
    }
    void inorder(Node* root)
    {
        if (root == NULL)return;
        inorder(root->left);
        root->left = pre;
        if (pre)
            pre->right = root;
        else head = root;
        pre = root;
        inorder(root->right);
    }
};

數組方法：很簡單就不做介紹瞭，就是先把節點都放進數組然後在建立聯系。

Node* treeToDoublyList(Node* root) {
        if (!root) return NULL;
        vector<Node*> nodelist;
        inorder(nodelist, root);
        int l = nodelist.size();
        if (l == 1)
        {
            nodelist[0]->right = nodelist[0];
            nodelist[0]->left = nodelist[0];
            return nodelist[0];
        }
        for (int i = 1; i < l - 1; i++) {
            nodelist[i]->left = nodelist[i - 1];
            nodelist[i]->right = nodelist[i + 1];
        }
        nodelist[0]->left = nodelist[l - 1];
        nodelist[0]->right = nodelist[1];
        nodelist[l - 1]->right = nodelist[0];
        nodelist[l - 1]->left = nodelist[l - 2];
        return nodelist[0];
    }
    void inorder(vector<Node*>& nodelist, Node* root)
    {
        if (root == NULL)return;
        inorder(nodelist, root->left);
        nodelist.push_back(root);
        inorder(nodelist, root->right);
    }

二叉搜索樹與雙向鏈表(C++中等區)

題目：輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的循環雙向鏈表。要求不能創建任何新的節點，隻能調整樹中節點指針的指向。

為瞭讓您更好地理解問題，以下面的二叉搜索樹為例：

在這裡插入圖片描述

我們希望將這個二叉搜索樹轉化為雙向循環鏈表。鏈表中的每個節點都有一個前驅和後繼指針。對於雙向循環鏈表，第一個節點的前驅是最後一個節點，最後一個節點的後繼是第一個節點。

下圖展示瞭上面的二叉搜索樹轉化成的鏈表。“head” 表示指向鏈表中有最小元素的節點。

在這裡插入圖片描述

特別地，我們希望可以就地完成轉換操作。當轉化完成以後，樹中節點的左指針需要指向前驅，樹中節點的右指針需要指向後繼。還需要返回鏈表中的第一個節點的指針。

解題思路

本文解法基於性質：二叉搜索樹的中序遍歷為 遞增序列 。

將 二叉搜索樹 轉換成一個 “排序的循環雙向鏈表” ，其中包含三個要素：

  • 排序鏈表：節點應從小到大排序，因此應使用 中序遍歷 “從小到大”訪問樹的節點；
  • 雙向鏈表：在構建相鄰節點（設前驅節點 pre ，當前節點 cur ）關系時，不僅應 pre.right =cur，也應 cur.left = pre 。
  • 循環鏈表：設鏈表頭節點 head 和尾節點 tail ，則應構建 head.left = tail， 和 tail.right = head 。

在這裡插入圖片描述

代碼展示

代碼如下：

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(!root) return NULL;
        mid(root);
        //進行頭節點和尾節點的相互指向，這兩句的順序也是可以顛倒的
        head->left=pre;
        pre->right=head;
        return head;
    }
    void mid(Node* cur)
    {
        if(!cur) return;
        mid(cur->left);
        //pre用於記錄雙向鏈表中位於cur左側的節點，即上一次迭代中的cur,當pre==null時，cur左側沒有節點,即此時cur為雙向鏈表中的頭節點
        if(pre==NULL) head=cur;
        //反之，pre!=null時，cur左側存在節點pre，需要進行pre.right=cur的操作。
        else pre->right=cur;
        //pre是否為null對這句沒有影響,且這句放在上面兩句if else之前也是可以的。
        cur->left=pre;
        //pre指向當前的cur
        pre=cur;
        //全部迭代完成後，pre指向雙向鏈表中的尾節點
        mid(cur->right);
    }
private:
    Node* head,*pre;
};
  • 執行用時：8 ms, 在所有 C++ 提交中擊敗瞭95.27%的用戶
  • 內存消耗：7.3 MB, 在所有 C++ 提交中擊敗瞭81.16%的用戶

以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持LevelAH。

推薦閱讀：