重建二叉树

引言

问题：现有二叉树的后序遍历序列与中序遍历序列，能否求原二叉树？

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

本文就如何使用这两种序列组合如何重建二叉树进行讨论。

首先，定义二叉树的遍历。

二叉树的遍历

对于一个二叉树的遍历，有以下原则：

- 遇到一个根节点，先访问左节点，再访问右节点

而前，后，中序遍历分别指根节点在访问左右节点之前，之间，之后。

如何重建？

那么根据二叉树遍历的定义，对一个最简单的只有一个根节点与左右节点的二叉树，来尝试重建。

设一个二叉树为下图左所示，它的前，中，后序遍历序列分别如下图右所示：

二叉树遍历

假设我们只知道后序与中序，如何重建呢？

1. 显然，后序的最后一个数字就是根节点，也就是 3 是根节点。
2. 在中序中找到3，它的左边是左节点，右边是右节点。
3. 最终重建到二叉树：根为3，左节点为7，右节点为1

由上方重建过程思考后，可以推广：

对于更复杂的二叉树，将其先看作上图模型的二叉树，重建得到根节点与暂时混乱的左右节点，再递归的将左右节点依次重建为子二叉树，即可完成整个二叉树的重建。

在得到根节点之后，需要在中序遍历序列中寻找根节点的位置，并将中序序列拆分为左右部分。所以要求序列中不能有相同的数字，这是序列可重建二叉树的前提。

编码抽象

将重建思路抽象之后，我们可以得到如下过程来重建二叉树：

定义二叉树节点

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

设有后序序列vector<int> post与中序序列vector<int> in，现在我们将二叉树重建到以TreeNode* node为根节点的二叉树中。

1. 取出post的最后一个数R，则R为二叉树的根节点
2. 在in中寻找R的位置
3. 从R拆分为左右子二叉树的中序序列：inleft、inright
4. 在post中，从左到右取出inleft.size()个数字，其组成的序列为左子二叉树的后序序列postleft
5. 类比4得到右子二叉树的后序序列postright
6. 分别根据inleft与postleft重建左子二叉树到node->left
7. 类比6重建右子二叉树到node->right

实现

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，大学生，技术宅，计算机科技爱好者，电音小王子。

我的博客：www.iimt.me

我在Weibo：@_iimT

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

想看到我的更多更新的话，很乐意你关注我！

你是谁？

欢迎在文后留下评论，一起讨论，欢迎认识新朋友。

如果你也有博客，在分享你的东西，欢迎交流、友链(本人博客底部可申请)。

下一篇见~