105. Construct Binary Tree from Preorder and Inorder Traversal

闭区间递归版 O(n) time

/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); ++i) {
            m[inorder[i]] = i;
        }
        return helper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }

    TreeNode *helper(const vector<int> &preorder, int pl, int pr, const vector<int> &inorder, int il, int ir) {
        if (pl > pr) return nullptr;
        auto res = new TreeNode(preorder[pl]);
        int lpl = pl + 1;
        int lir = m[preorder[pl]] - 1;
        int lil = il;
        int lpr = lpl + lir - lil;
        res->left = helper(preorder, lpl, lpr, inorder, lil, lir);
        int rpl = lpr + 1;
        int rpr = pr;
        int ril = lir + 2;
        int rir = ir;
        res->right = helper(preorder, rpl, rpr, inorder, ril, rir);
        return res;
    }

    unordered_map<int, int> m;
};

开区间递归memo版O(n) time

/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (auto it = begin(inorder); it != end(inorder); ++it) {
            m[*it] = it;
        }
        return helper(begin(preorder), end(preorder), begin(inorder), end(inorder));
    }

    using It = vector<int>::iterator;
    TreeNode *helper(It pb, It pe, It ib, It ie) {
        if (pb == pe) return nullptr;
        auto res = new TreeNode(*pb);
        auto it = m[*pb];
        int d = distance(ib, it);
        res->left = helper(pb + 1, pb + d + 1, ib, it);
        res->right = helper(pb + d + 1, pe, it + 1, ie);
        return res;
    }

    unordered_map<int, It> m;
};

开区间递归版O(n²) time

/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return helper(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }

    using Iter = vector<int>::iterator;

    TreeNode *helper(Iter pb, Iter pe, Iter ib, Iter ie) {
        if (pb >= pe || ib >= ie) return nullptr;
        int v = *pb;
        TreeNode *root = new TreeNode(v);
        auto it = find(ib, ie, v);
        int dist = distance(ib, it);
        root->left = helper(pb + 1, pb + dist + 1, ib, it);
        root->right = helper(pb + dist + 1, pe, it + 1, ie);
        return root;
    }
};

闭区间递归版O(n²) time

/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int pn = preorder.size(), in = inorder.size();
        return helper(preorder, 0, pn - 1, inorder, 0, in - 1);
    }

    TreeNode *helper(const vector<int> &p, int pl, int pr, const vector<int> &i, int il, int ir) {
        if (pl > pr || il > ir) return nullptr;
        int v = p[pl];
        TreeNode *root = new TreeNode(v);
        int ri = il;
        for (int j = il; j <= ir; ++j) {
            if (i[j] == v) {
                ri = j;
                break;
            }
        }
        root->left = helper(p, pl + 1, pl + ri - il, i, il, ri - 1);
        root->right = helper(p, pr + ri - ir + 1, pr, i, ri + 1, ir);
        return root;
    }
};