题解 | #重建二叉树#

边界一定要处理好

前序里左子树的长度和中序是一样的，所以直接跳过相同长度即可。

/**
 * 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 || rl > rr) return nullptr;
        
        cout << ll << lr << rl << rr << endl;
        auto p = new TreeNode(pre[ll]);
        for(int i = rl; i <= rr; i++) {
            if(vin[i] == pre[ll]) {
                p->left = build(pre, vin, ll+1, ll + i - rl, rl, i - 1);
                p->right = build(pre,vin, ll + i - rl + 1, lr,  i + 1, rr);
            }
        }
        return p;
    }
};