题解 | #重建二叉树#

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 */
#include <vector>
class Solution {
public:
    void p(TreeNode* t) {
        if (t) {
            cout << t->val << " ";
            p(t->left);
            p(t->right);
        }
    }
    TreeNode* create(vector<int> pre, int l1, int r1, vector<int> in, int l2, int r2) {
        int mid;
        for (int i = 0; i < in.size(); i++) {
            if (in[i] == pre[l1]) {
                mid = i;
                break;
            }
        }
        TreeNode* node = new TreeNode(pre[l1]);
        int llen = mid - l2;
        int rlen = r2 - mid;
        if (llen > 0) {
            node->left = create(pre, l1 + 1, l1 + llen, in, l2, l2 + llen - 1);
        }
        else node->left = nullptr;
        if (rlen > 0) {
            node->right = create(pre, l1 + 1 + llen, r2, in, l2 + llen + 1, r2);
        }
        else node->right = nullptr;
        return node;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
        if (pre.size() == 0) return nullptr;
        return create(pre, 0, pre.size()-1, vin, 0, vin.size()-1);
    }
};