1 问题

从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

2 解法

与给定中序数组与后序数组构造二叉树类似，只是此时前序数组的第一个节点为根节点。

/**
 * 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* traversal(vector<int>& preorder, vector<int>& inorder)
    {
        if(preorder.size() == 0)
            return NULL;
        //1.前序数组的第一个节点为根节点
        int rootVal = preorder[0];
        TreeNode* root = new TreeNode(rootVal);
        //递归结束条件,前序数组仅剩一个元素，此时为叶子节点
        if(preorder.size() == 1)
            return root;
        //2. 根据根节点切割中序数组
        //2.1. 找到根节点在中序数组中的位置
        int delimiterIndex;
        for(delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++)
        {
            if(inorder[delimiterIndex] == rootVal)
                break;
        } 
        //2.2. 切分中序数组
        //左部分[0, delimiterIndex)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        //右部分[delimiterIndex+1, end)
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end());
        //3.根据中序数组的长度，切分前序数组
        //前序数组去除根节点(第一个元素)
        preorder.erase(preorder.begin());
        //左部分[begin, begin + size)
        vector<int> leftPreorder(preorder.begin(), preorder.begin() + leftInorder.size());
        //右部分[begin + size, end）
        vector<int> rightPreorder(preorder.begin() + leftInorder.size(), preorder.end());
        //4.递归
        root->left = traversal(leftPreorder, leftInorder);
        root->right = traversal(rightPreorder, rightInorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0 || inorder.size() == 0)
            return NULL;
        return traversal(preorder, inorder);
    }
};