LeetCode-Construct Binary Tree From Preorder and Inorder Traversal

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

方法比较常规，根据前序遍历中的节点将中序遍历的节点分为两部分，这就是该节点的左子树和右子树，然后使用递归不断建立新的子树即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pre_l, int pre_r, int in_l, int in_r) {
        if(pre_l>pre_r || in_l>in_r) return nullptr;
        int root_val = preorder[pre_l];
        TreeNode* root = new TreeNode(root_val);
        int in_split_pos = in_l;
        for(int i=in_l; i<=in_r; ++i) {
            if(inorder[i] == root_val) {
                in_split_pos = i;
                break;
            }
        }
        int diff = in_split_pos - in_l;
        root->left = build(preorder, inorder, pre_l+1, pre_l+diff, in_l, in_split_pos-1);
        root->right = build(preorder, inorder, pre_l+diff+1, pre_r, in_split_pos+1, in_r);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int len = preorder.size();
        if(len == 0) return nullptr;
        return build(preorder, inorder, 0, len-1, 0, len-1);
    }
};