题目描述

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

思路

根据先序和中序可以划分左右子树，递归构造子树即可。

代码

class Solution {
public:
    TreeNode* buildSubTree(vector<int>& preorder, vector<int>& inorder, int p_start, int i_start, int i_end) {
        if(p_start>preorder.size()-1||i_start<0||i_start>i_end) return nullptr;
        TreeNode* root=new TreeNode(preorder[p_start]);
        if(i_start==i_end)
            return root;
        int i=i_start;
        while(inorder[i]!=preorder[p_start])i++;
        root->left = buildSubTree(preorder, inorder, p_start+1, i_start, i-1);
        root->right = buildSubTree(preorder, inorder,p_start+(i-i_start+1), i+1, i_end);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildSubTree(preorder, inorder,0,0,inorder.size()-1);
    }
};