题解 | #重建二叉树#

调了半天发现，没有左子树和右子树的处理不好。。。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        TreeNode* root = nullptr;
        if(!pre.size()) return root;
        root = build(pre, vin, 0, pre.size() - 1, 0, vin.size() - 1);
        return root;
    }
    TreeNode* build(vector<int> pre,vector<int> vin, int ll, int lr, int rl, int rr){ 
        if(ll == lr) return new TreeNode(pre[ll]);

        cout << ll << lr << rl << rr <<endl;
        TreeNode* p = nullptr;
        int in = 0;
        int flag[20005] ={0};
        
        for(int i = rl; i <= rr; i++) {     
            flag[vin[i] + 10000] += 1;
            if(pre[ll] == vin[i]) {
                in = i;
                break;
            }   
        }

        int re = -1;
        for(int i = ll; i <= lr; i++) {
            if(flag[pre[i] + 10000] == 0) {
                re = i;
                break;
            }
        }
        if(re == -1) re = lr + 1;
        p = new TreeNode(pre[ll]);
        if(in != rl) p->left = build(pre, vin, ll + 1, re - 1, rl, in - 1);
        if(in != rr) p->right = build(pre, vin, re, lr, in + 1, rr);
        return p;
    }
};