题目描述

image.png

题解

前序遍历：首先访问根节点，然后遍历左子树，最后遍历右子树
中序遍历：首先遍历左子树，然后访问根节点，最后遍历右子树

根据上述规则，使用递归的方法：

• 首先，前序遍历序列里的第一个元素就是根节点，后面依次是左子树的前序遍历序列加右子树的前序遍历序列，但此时不知道左子树的元素个数，所以无法确定分界点
• 然后在中序遍历序列中找到根节点对应的元素，根节点前面就是左子树的中序遍历序列，根节点后面就是右子树的中序遍历序列
• 在中序遍历序列里求出左子树的元素个数，然后在前序遍历序列里划分出左右子树
• 这样就得到了左右子树的前序遍历和中序遍历序列，然后对左右子树递归求解

这里使用iterator来做vector的划分（用下标也行），iterator的使用：
定义vector和iterator

vector<int> vec;
vector<int>::iterator it;

iterator的使用类似于指针，支持与数字相加，也支持自增运算符

for(vertor<int>::iterator it = vec.begin(); it != vec.end(); it++)
{
   cout << *it << endl;
}

代码

// reConstructBinaryTree.cpp
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    ~TreeNode() {
        if (this->left != NULL) {
            delete this->left;
            this->left = NULL;
        }
        if (this->right != NULL) {
            delete this->right;
            this->right = NULL;
        }
    }
};

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return reConstructBinaryTree(pre.begin(), pre.end(), vin.begin(), vin.end());
    }
private:
    TreeNode* reConstructBinaryTree(vector<int>::iterator pre_begin, vector<int>::iterator pre_end,
            vector<int>::iterator vin_begin, vector<int>::iterator vin_end){
        if (pre_begin == pre_end){
            return NULL;
        }
        TreeNode* root = new TreeNode(*pre_begin);
        vector<int>::iterator i;
        int num_left = 0;
        for (i = vin_begin; i != vin_end; i++){
            if (*i == *pre_begin){
                break;
            }
            num_left++;
        }
        root->left = reConstructBinaryTree(pre_begin + 1, pre_begin + 1 + num_left, vin_begin, vin_begin + num_left);
        root->right = reConstructBinaryTree(pre_begin + num_left + 1, pre_end, vin_begin + num_left + 1, vin_end);
        return root;
    }
};
void preorderPrintTree(TreeNode* root){
    if (root == NULL){
        return;
    }
    cout << root->val << " ";
    preorderPrintTree(root->left);
    preorderPrintTree(root->right);
}
void inorderPrintTree(TreeNode* root){
    if (root == NULL){
        return;
    }
    inorderPrintTree(root->left);
    cout << root->val << " ";
    inorderPrintTree(root->right);
}

int main(){
    vector<int> pre = {1,2,4,7,3,5,6,8};
    vector<int> vin = {4,7,2,1,5,3,8,6};
    Solution s;
    TreeNode* root = s.reConstructBinaryTree(pre, vin);
    cout << "preorder: ";
    preorderPrintTree(root);
    cout << endl;
    cout << "inorder: ";
    inorderPrintTree(root);
    cout << endl;

    delete root;

    return 0;
}