重建二叉樹

引言

問題：現(xiàn)有二叉樹的后序遍歷序列與中序遍歷序列，能否求原二叉樹？

答案是肯定的，并且前序與中序也可以得到原二叉樹。

本文就如何使用這兩種序列組合如何重建二叉樹進(jìn)行討論。

首先，定義二叉樹的遍歷。

二叉樹的遍歷

對(duì)于一個(gè)二叉樹的遍歷，有以下原則：

- 遇到一個(gè)根節(jié)點(diǎn)，先訪問左節(jié)點(diǎn)，再訪問右節(jié)點(diǎn)

而前，后，中序遍歷分別指根節(jié)點(diǎn)在訪問左右節(jié)點(diǎn)之前，之間，之后。

如何重建？

那么根據(jù)二叉樹遍歷的定義，對(duì)一個(gè)最簡單的只有一個(gè)根節(jié)點(diǎn)與左右節(jié)點(diǎn)的二叉樹，來嘗試重建。

設(shè)一個(gè)二叉樹為下圖左所示，它的前，中，后序遍歷序列分別如下圖右所示：

二叉樹遍歷

假設(shè)我們只知道后序與中序，如何重建呢？

1. 顯然，后序的最后一個(gè)數(shù)字就是根節(jié)點(diǎn)，也就是 3 是根節(jié)點(diǎn)。
2. 在中序中找到3，它的左邊是左節(jié)點(diǎn)，右邊是右節(jié)點(diǎn)。
3. 最終重建到二叉樹：根為3，左節(jié)點(diǎn)為7，右節(jié)點(diǎn)為1

由上方重建過程思考后，可以推廣：

對(duì)于更復(fù)雜的二叉樹，將其先看作上圖模型的二叉樹，重建得到根節(jié)點(diǎn)與暫時(shí)混亂的左右節(jié)點(diǎn)，再遞歸的將左右節(jié)點(diǎn)依次重建為子二叉樹，即可完成整個(gè)二叉樹的重建。

在得到根節(jié)點(diǎn)之后，需要在中序遍歷序列中尋找根節(jié)點(diǎn)的位置，并將中序序列拆分為左右部分。所以要求序列中不能有相同的數(shù)字，這是序列可重建二叉樹的前提。

編碼抽象

將重建思路抽象之后，我們可以得到如下過程來重建二叉樹：

定義二叉樹節(jié)點(diǎn)

struct TreeNode {
    int data;
    TreeNode* left = NULL;
    TreeNode* right = NULL;
};

設(shè)有后序序列vector<int> post與中序序列vector<int> in，現(xiàn)在我們將二叉樹重建到以TreeNode* node為根節(jié)點(diǎn)的二叉樹中。

1. 取出post的最后一個(gè)數(shù)R，則R為二叉樹的根節(jié)點(diǎn)
2. 在in中尋找R的位置
3. 從R拆分為左右子二叉樹的中序序列：inleft、inright
4. 在post中，從左到右取出inleft.size()個(gè)數(shù)字，其組成的序列為左子二叉樹的后序序列postleft
5. 類比4得到右子二叉樹的后序序列postright
6. 分別根據(jù)inleft與postleft重建左子二叉樹到node->left
7. 類比6重建右子二叉樹到node->right

實(shí)現(xiàn)

void getTree(vector<int> post, vector<int> in, TreeNode* node) {
    vector<int> inleft, inright;
    vector<int> postleft, postright;
    if (post.size() == 0) return;
    int rootNum = post[post.size() - 1];
    post.pop_back();
    node->data = rootNum;
    // 將中序遍歷拆開
    bool flag = false;
    for (int i = 0; i < in.size(); i++) {
        if (in[i] == rootNum) {
            flag = true;
            continue;
        }
        if (!flag)
            inleft.push_back(in[i]);
        else
            inright.push_back(in[i]);
    }
    // 將后序遍歷拆開
    for (int i = 0; i < post.size(); i++) {
        if (i < inleft.size()) {
            postleft.push_back(post[i]);
        } else {
            postright.push_back(post[i]);
        }
    }

    if (inleft.size() > 0) {
        node->left = new TreeNode;
        getTree(postleft, inleft, node->left);
        
    }

    if (inright.size() > 0) {
        node->right = new TreeNode;
        getTree(postright, inright, node->right);
    }
}

全文完。

我是誰？

我是iimT，大學(xué)生，技術(shù)宅，計(jì)算機(jī)科技愛好者，電音小王子。

我的博客：www.iimt.me

我在Weibo：@_iimT

我在B站：https://space.bilibili.com/69824765/#/

想看到我的更多更新的話，很樂意你關(guān)注我！

你是誰？

歡迎在文后留下評(píng)論，一起討論，歡迎認(rèn)識(shí)新朋友。

如果你也有博客，在分享你的東西，歡迎交流、友鏈(本人博客底部可申請(qǐng))。

下一篇見~