二叉树 – 从前序和中序序列构造二叉树

从前序和中序序列构造二叉树主要是考查对二叉树的前序、中序和构造二叉树知识的理解。

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

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

该题和从中序和后序序列构造二叉树题目类似。

解题思路（构造顺序为先序构造）：

• 1 从先序序列中定位到根节点，并建立root节点，同时判断是否先序序列的size是否为1，为1则直接返回root即可。
• 2 从中序序列中定位到根节点位置。
• 3 拆分中序序列为左子树数组和右子树数组。
• 4 拆分先序序列为左子树数组和右子树的数组。（先拆分中序是因为需要依靠中序拆分后的左右子数组的长度来定位）
• 5 进行递归构造二叉树。

详细代码：

class Solution {
public:
    TreeNode* traversal(vector<int>& preorder, vector<int>& inorder){
        if (preorder.size() == 0) return nullptr;
        // 1 从preorder找到和构建根节点
        int rootValue = preorder[0];
        TreeNode* root = new TreeNode(rootValue);
        if (preorder.size() == 1) return root;

        // 2 从inorder中找到根节点
        int delimiter;
        for(delimiter=0; delimiter<inorder.size(); delimiter++){
            if (inorder[delimiter] == rootValue) break;
        }

        // 3 切割inorder
        vector<int> leftInorder(inorder.begin(), inorder.begin()+delimiter);
        vector<int> rightInorder(inorder.begin()+delimiter+1, inorder.end());

        // 4 切割preorder
        vector<int> leftPreorder(preorder.begin()+1, preorder.begin()+leftInorder.size()+1); 
        vector<int> rightPreorder(preorder.begin()+leftInorder.size()+1, preorder.end());

        // 5 递归
        root->left = traversal(leftPreorder, leftInorder);
        root->right = traversal(rightPreorder, rightInorder);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (!preorder.size() || !inorder.size()) return nullptr;
        return traversal(preorder, inorder);
    }
};