題目描述

image.png

題解

前序遍歷：首先訪問(wèn)根節(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)
中序遍歷：首先遍歷左子樹(shù)，然后訪問(wèn)根節(jié)點(diǎn)，最后遍歷右子樹(shù)

根據(jù)上述規(guī)則，使用遞歸的方法：

• 首先，前序遍歷序列里的第一個(gè)元素就是根節(jié)點(diǎn)，后面依次是左子樹(shù)的前序遍歷序列加右子樹(shù)的前序遍歷序列，但此時(shí)不知道左子樹(shù)的元素個(gè)數(shù)，所以無(wú)法確定分界點(diǎn)
• 然后在中序遍歷序列中找到根節(jié)點(diǎn)對(duì)應(yīng)的元素，根節(jié)點(diǎn)前面就是左子樹(shù)的中序遍歷序列，根節(jié)點(diǎn)后面就是右子樹(shù)的中序遍歷序列
• 在中序遍歷序列里求出左子樹(shù)的元素個(gè)數(shù)，然后在前序遍歷序列里劃分出左右子樹(shù)
• 這樣就得到了左右子樹(shù)的前序遍歷和中序遍歷序列，然后對(duì)左右子樹(shù)遞歸求解

這里使用iterator來(lái)做vector的劃分（用下標(biāo)也行），iterator的使用：
定義vector和iterator

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

iterator的使用類(lèi)似于指針，支持與數(shù)字相加，也支持自增運(yùn)算符

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;
}