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

两天宇宙人

2020-02-20

😂递归

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return helper(preorder, inorder, 0, 0, inorder.size() - 1);
    }
    TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int p, int ib, int ie){
        if(ib > ie || p >= preorder.size()) 
            return nullptr;
        int node_val = preorder[p];
        int in_mid = -1;
        for(int i = ib; i <= ie; ++i) 
            if(inorder[i] == node_val) {
                in_mid = i;
                break;
            }
        TreeNode* node = new TreeNode(node_val);
        node->left = helper(preorder, inorder, p + 1, ib, in_mid - 1);
        node->right = helper(preorder, inorder, p + 1 + in_mid - ib, in_mid + 1, ie);
        return node;
    }
};