[数据结构] 根据前中后序遍历中的两种构造二叉树

前中后序遍历的特点

前序遍历

前序遍历顺序：根节点 -> 左子树 -> 右子树
前序遍历结果：[根节点，[左子树前序遍历结果]，[右子树前序遍历结果]]
假如把前序遍历结果存到数组中，数组中的第一个元素就是二叉树根节点的数据，而且还可以知道第二个元素是根节点左孩子的数据，即左子树根节点的数据。

中序遍历

中序遍历顺序：左子树 -> 根节点 -> 右子树
中序遍历结果：[[左子树中序遍历结果]，根节点，[右子树中序遍历结果]]
将中序遍历结果存储到数组中，如果我们知道了根节点的下标，可以判断二叉树左子树节点的个数和右子树的个数。

后序遍历

后序遍历顺序：左子树 -> 右子树 -> 根节点
后序遍历结果：[[左子树后序遍历结果]，[右子树后序遍历结果]，根节点]
将后序遍历结果存储倒数组中，可以发现数组的最后一个元素是二叉树根节点的数据，而且也可以知道倒数第二个元素是根节点右孩子数据，即右子树根节点的数据。

根据两种遍历方式构造二叉树的可行性

根据两种遍历的结果来构造二叉树，前提是这两种遍历结果一定是同一颗二叉树遍历的结果，而且二叉树的每个节点值都是唯一的，也就是说不存在重复元素。

---

前序 + 中序构造二叉树

前序遍历 + 中序遍历思路

前序遍历：[根节点，[左子树前序遍历结果]，[右子树前序遍历结果]]
中序遍历：[[左子树中序遍历结果]，根节点，[右子树中序遍历结果]]
根据前序遍历可以知道根节点的数据，然后在中序遍历的结果中根据这个值定位到根节点位置。假设定位到中序遍历根节点下标为 index_mid ，那么就可以确定左子树节点个数 left_num 为 index_mid - in_left ，右子树节点个数 right_num 为 in_right - index_mid ，其中 in_left 为当前二叉树中序遍历的左边界， in_right 为当前二叉树中序遍历的右边界。(在实际运用过程中，其实只用到左子树节点个数就可以了)

大致思路我们知道了，根据左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，可以递归来求解左子树和右子树，所以我们只需要再分别递归对左子树对应范围和右子树对应范围进行同样的操作就可以了。

在中序遍历中定位根节点，可以在中序遍历中扫描一遍，当出现值相等时，记录下标。但是这个方法比较低效，我们用更加高效的办法来完成根节点在中序遍历中的定位。我们构造一个哈希映射，记录节点值在中序遍历中对应的下标位置，即键为节点值，值为中序遍历中对应的下标。我们事先记录节点在中序遍历中的下标，当我们知道了根节点的数值时，就可以在 O(1) 的时间复杂度找到其在中序遍历中的位置 index_mid。

大致步骤为：
得到根节点在中序遍历中的位置 index_mid，pre_left 为前序遍历左边界，pre_right 为前序遍历右边界
（1）root = new TreeNode(root_val)
（2）root->left = func(pre_left + 1, pre_left + left_num, in_left, index_mid - 1)
（3）root->right = func(pre_left + left_num + 1, pre_right, index_mid + 1, in_right)

前序 + 中序构造二叉树图解

（1）

（2）

（3）

（4）

（5）

（6）

前序 + 中序构造二叉树代码

在leetcode上有相关题目，代码也是此题目对应的解答。从前序与中序遍历序列构造二叉树

class Solution {
    unordered_map<int, int> hash;
public:
    TreeNode* build(vector<int>& pre, vector<int> &in, int pre_left, int pre_right, int in_left, int in_right){
        if(in_left > in_right || pre_left > pre_right) return NULL;
        int root_val = pre[pre_left];        //前序遍历第一个为根节点
        int index_mid = hash[root_val];      //根节点在中序遍历中对应的下标
        int left_num = index_mid - in_left;  //左子树节点个数

        TreeNode *root = new TreeNode(root_val);
        root->left = build(pre, in, pre_left + 1, pre_left + left_num, in_left, index_mid - 1);
        root->right = build(pre, in, pre_left + left_num + 1, pre_right, index_mid + 1, in_right);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = inorder.size();
        for(int i = 0; i < n; i++) hash[inorder[i]] = i;
        return build(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

---

中序 + 后序构造二叉树

中序遍历 + 后序遍历思路

中序遍历结果：[[左子树中序遍历结果]，根节点，[右子树中序遍历结果]]
后序遍历结果：[[左子树后序遍历结果]，[右子树后序遍历结果]，根节点]
和前序遍历 + 中序遍历构造二叉树的思路有些类似，我们可以根据后序遍历最后一个元素知道二叉树根节点的数值，然后在中序遍历结果中定位。假设定位下标位置为 index_mid，可以确定左子树节点个数 left_num 为 index_mid - in_left ，右子树节点个数 right_num 为 in_right - index_mid ，其中 in_left 为当前二叉树中序遍历的左边界， in_right 为当前二叉树中序遍历的右边界。

根据左子树的中序遍历和后序遍历结果，以及右子树的中序遍历和后序遍历结果，递归来求解左子树和右子树。

记录下标同样是构造哈希映射来记录中序遍历结果的键值对。

大致步骤为：
得到根节点在中序遍历中的位置 index_mid，post_left 为后序遍历左边界，post_right 为后序遍历右边界。
（1）root = new TreeNode(root_val)
（2）root->left = func(in_left, index_mid - 1, post_left + 1, post_left + left_num - 1)
（3）root->right = func(index_mid + 1, in_right, post_left + left_num, post_right - 1)

中序 + 后序构造二叉树图解

（1）

（2）

（3）

（4）

（5）

（6）

中序 + 后序构造二叉树代码

在leetcode上有相关题目，代码也是此题目对应的解答。从中序与后序遍历序列构造二叉树

class Solution {
    unordered_map<int, int> hash;
public:
    TreeNode* build(vector<int>& in, vector<int>& post, int in_left, int in_right, int post_left, int post_right){
        if(in_left > in_right || post_left > post_right) return NULL;
        int root_val = post[post_right];    //后序遍历的最后一个为根节点
        int index_mid = hash[root_val];     //根节点在中序遍历中对应下标
        int left_num = index_mid - in_left; //左子树节点个数

        TreeNode *root = new TreeNode(root_val);
        root->left = build(in, post, in_left, index_mid - 1, post_left, post_left + left_num - 1);
        root->right = build(in, post, index_mid + 1, in_right, post_left + left_num, post_right - 1);
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        for(int i = 0; i < n; i++) hash[inorder[i]] = i;
        return build(inorder, postorder, 0, n - 1, 0, n - 1);
    }
};

---

前序 + 后序构造二叉树 *

前序遍历 + 后序遍历思路 *

前序遍历结果：[根节点，[左子树前序遍历结果]，[右子树前序遍历结果]]
后序遍历结果：[[左子树后序遍历结果]，[右子树后序遍历结果]，根节点]
前序遍历 + 后序遍历相比前两种要特殊一些，这个组合可以构造二叉树，但是根据前序遍历和后序遍历是无法确定唯一的二叉树的。
我们知道前序遍历第一个是根节点，后序遍历最后一个是根节点，光靠这两个信息无法构造二叉树。但是我们可以知道一般前序遍历的第二个元素是左子树根节点的值，后序遍历的倒数第二个元素一般是右子树根节点的值，我们可以由此来确定左右子树的节点个数。（注意是一般情况下是这样，当没有左子树时，前序遍历的第二个应当为右子树根节点数值，后续便利同样也存在这样的问题，这也是后面为什么写了无法确定唯一二叉树的一个原因）实际上，我们只需要用其中一个子树根节点就可以了，以已知左子树根节点为例，假如我们知道了左子树根节点元素在后序遍历中对应的下标为 index_mid，那么可以得到左子树节点个数 left_num 为 index_mid - post_left，右子树节点个数 right_num 为 post_right - 1 - index_mid。对于左子树根节点的定位，我们只需要构造对二叉树后序遍历的哈希映射就可以了。根据后序遍历已知右子树根节点同理。

根据左子树的前序遍历和后序遍历结果，以及右子树的前序遍历和后序遍历结果，递归来求解左子树和右子树。

大致步骤为：
（1）root = new TreeNode(root_val)
（2）root->left = func(pre_left + 1, pre_left + left_num, post_left, index_mid)
（3）root->right = func(pre_left + left_num + 1, pre_right, index_mid + 1, post_right - 1)

但是这无法确定唯一二叉树，我们可以举个例子来看一下。
假如某个二叉树的前序遍历结果为 [1, 2, 4, 3]，后序遍历结果为 [4, 2, 3, 1]。
根据上面的方式可以得到根节点数值是1，左子树根节点数值是2，在后序遍历中定位后可以得到左子树后续遍历结果为 [4, 2] ，再对其进行递归操作，默认得到的是4为2的左孩子。但是实际上4为2的右孩子的话，也是满足上面前序遍历和后序遍历的结果的。

不过当二叉树不存在度数为 1 的节点时，前序遍历 + 后序遍历是可以确定唯一的二叉树的。

前序 + 后序构造二叉树图解

（1）

（2）

（3）

（4）

（5）

（6）

前序 + 后序构造二叉树代码

在leetcode上有相关题目，代码也是此题目对应的解答。根据前序和后序遍历构造二叉树

class Solution {
    unordered_map<int, int> hash;
public:
    TreeNode* build(vector<int>& pre, vector<int>& post, int pre_left, int pre_right, int post_left, int post_right){
        if(pre_left > pre_right || post_left > post_right) return NULL;
        if(pre_left == pre_right) return new TreeNode(pre[pre_left]);
        int root_val = pre[pre_left], left_root = pre[pre_left + 1];
        //根节点    左子树根节点
        int index_mid = hash[left_root];
        int left_num = index_mid - post_left + 1;

        TreeNode *root = new TreeNode(root_val);
        root->left = build(pre, post, pre_left + 1, pre_left + left_num, post_left, index_mid);
        root->right = build(pre, post, pre_left + left_num + 1, pre_right, index_mid + 1, post_right - 1);
        return root;
    }

    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        int n = preorder.size();
        for(int i = 0; i < n; i++) hash[postorder[i]] = i;
        return build(preorder, postorder, 0, n - 1, 0, n - 1);
    }
};