【C++】前序中序（或后序遍历）构造二叉树

一、背景

每次用前序与中序或是中序与后序遍历来构造二叉树的问题，其实思路挺清晰的就是找出每个位置的父节点，然后递归，就是每次写出来下次怎么实现的又搞不清楚了，记录下来以后能快速的回想起来respect！！！

二、解题思路

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

思路还是比较清晰的，首先我们明白前序遍历的第一个节点就是根节点，然后根据这个信息，从中序遍历中找出左右子树的范围，然后去递归实现。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

        return buildTree(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
    TreeNode* buildTree(vector<int>& preorder, int l1, int r1, vector<int>& inorder, int l2, int r2) {
        if (l1>r1 || l2>r2) return nullptr;
        int root = preorder[l1];
        int mid = l2;
        while (inorder[mid]!=root) mid++;

        TreeNode* s = new TreeNode(root);

        int x = mid-l2; // 这里是左半部分的长度
        s->left = buildTree(preorder, l1+1, l1+x, inorder, l2, mid-1);
        s->right = buildTree(preorder, l1+x+1, r1, inorder, mid+1, r2);

        return s;
    }
};

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

这个本质上与上边的题目是一样的求解方法，只不过这里提供根节点信息的是后序遍历，后序遍历的最后一个节点就是根节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return buildTree(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder, int l1, int r1, int l2, int r2) {
        if (l1>r1 || l2>r2) return nullptr;
        int root = postorder[r2];
        int mid = l1;
        while (inorder[mid]!=root) mid++;

        TreeNode* s = new TreeNode(root);

        int x = mid-l1;
        s->left = buildTree(inorder, postorder, l1, mid-1, l2,  l2+x-1);
        s->right = buildTree(inorder, postorder, mid+1, r1, l2+x,r2-1);

        return s;
    }
};