题解 | #重建二叉树#

class Solution {
  public:
    TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
        int size_vin = vin.size();
        int size_pre = pre.size();
        TreeNode* root = new TreeNode(0);
        if (size_vin == 0 || size_pre == 0) {
            return NULL;
        } else if (size_vin == 1 && size_pre == 1) {
            root->val = vin[0];
            return root;
        }


        for (int i = 0; i < size_vin; i++) {
            if (pre[0] == vin[i]) {
                cout << i << endl;
                vector<int> test(pre.begin(), pre.end());
                for (auto i = test.begin(); i < test.end(); i++) {
                    cout << *i << endl;
                }

                vector<int> pre_left(pre.begin() + 1, pre.begin() + i + 1);
                for (auto i = pre_left.begin(); i < pre_left.end(); i++) {
                    cout << *i << endl;
                }
                cout << "___________________" << endl;
                vector<int> pre_right(pre.begin() + i + 1, pre.end());
                for (auto i = pre_right.begin(); i < pre_right.end(); i++) {
                    cout << *i << endl;
                }
                cout << "___________________" << endl;
                vector<int> vin_left(vin.begin(), vin.begin() + i);
                for (auto i = vin_left.begin(); i < vin_left.end(); i++) {
                    cout << *i << endl;
                }
                cout << "___________________" << endl;
                vector<int> vin_right(vin.begin() + i + 1, vin.end());
                for (auto i = vin_right.begin(); i < vin_right.end(); i++) {
                    cout << *i << endl;
                }
                cout << vin[i] << endl;
                root->val = vin[i];
                cout << i << endl;
                root->left = reConstructBinaryTree(pre_left, vin_left);
                root->right = reConstructBinaryTree(pre_right, vin_right);
            }

        }
        return root;
    }
};