106. 从中序与后序遍历序列构造二叉树、105. 从前序与中序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树

题目描述：

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

解答：

首先来理清如何手动实现从中序、后序遍历序列构造二叉树。

中序遍历：左中右，后序遍历：左右中。

后序序列中的最后一个即为根节点，然后根据此根节点划分中序序列，得到左子树、右子树；然后再根据中序序列划分出的左右子树去划分后序序列。划分完毕后递归执行即可。

梳理一下整体的步骤：

第一步：如果数组大小为0，说明是空直接返回

第二步：数组不为空，取中序序列的最后一个值，该值即为根节点

第三步：在中序序列中找到划分点

第四步：根据划分点对中序序列进行划分

第五步：根据中序序列再划分后序序列

第六步：递归执行

那么下一个问题来了，我们应该如何去划分中序序列？

此时应该注意确定切割的标准，是左闭右开，还有左开右闭，还是左闭右闭，这个就是不变量，要在递归中保持这个不变量。此处考虑到vector.end()的性质，采用左闭右开的方式。

vectorleftInorder(inorder.begin(), inorder.begin() + devide);
vectorrightInorder(inorder.begin() + devide + 1, inorder.end());

划分后序序列又应该如何实现？

在划分中序序列后实际上我们已经得到了左右子树有哪些值，所以只需要那种左右子树的长度对后序序列进行划分即可。

需要额外注意的是后序序列的最后一个元素不参与划分，因为其为根节点。

postorder.resize(postorder.size() - 1);
// 第五步：切割后序数组，得到后序左数组和后序右数组
vectorleftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
vectorrightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

 代码实现：

class Solution {
public:
    TreeNode* traversal(vector& inorder, vector& postorder) {
        
        //第一步：如果数组大小为零的话，说明是空节点了
        if(postorder.size() == 0)
            return NULL;
        //第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
        int rootVal = postorder[postorder.size()-1];
        TreeNode* root = new TreeNode(rootVal);

        if (postorder.size() == 1) return root;

        //第三步，在中序序列中找到划分点
        int devide;
        for (devide = 0; devideleftInorder(inorder.begin(), inorder.begin() + devide);
        vectorrightInorder(inorder.begin() + devide + 1, inorder.end());

        postorder.resize(postorder.size() - 1);
        // 第五步：切割后序数组，得到后序左数组和后序右数组
        vectorleftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        vectorrightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
        
        // 第六步递归调用
        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);

        return root;
    }
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};

105. 从前序与中序遍历序列构造二叉树

题目描述：

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

解答：

整体思路和106题一致。

先序序列：中左右；中序序列：左右中。

先序序列的第一个值即为根节点，拿到根节点后在中序序列中找到划分位置，将中序序列划分为左右子序列。再根据左右子序列的长度划分根节点以外的先序序列。最后递归调用即可。

代码实现：

class Solution {
public:

    TreeNode* buildTree(vector& preorder, vector& inorder) {
        if (preorder.size() == 0)
            return NULL;
        
        int rootVal = preorder[0];
        TreeNode* root = new TreeNode(rootVal);

        int devide = 0;
        for (; devideleftInorder(inorder.begin(), inorder.begin()+devide);
        vectorrightInorder(inorder.begin()+devide+1, inorder.end());

        vectorleftPreorder(preorder.begin()+1, preorder.begin()+1+leftInorder.size());
        vectorrightPreorder(preorder.begin()+1+leftInorder.size(), preorder.end());
        
        root->left = buildTree(leftPreorder, leftInorder);
        root->right = buildTree(rightPreorder, rightInorder);

        return root;
    }
};