题目
思路
Code
/** * 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) { int prelen = pre.size(); if(prelen == 0) //递归终止条件: 前序数组,中序数组为0, 返回值为NULL return NULL; vector<int> preleft, preright, vinleft, vinright; //子前序序列,子中序序列 int gen; TreeNode *root = new TreeNode(pre[0]); //寻找根在中序序列数组中的位置 for(int i = 0; i < prelen; i++) { if(vin[i] == pre[0]) { gen = i; break; } } //填充左子前序序列 [1, gen],左子中序序列 for(int i = 1; i <= gen; i++) { preleft.push_back(pre[i]); vinleft.push_back(vin[i-1]); } //填充右子前序序列 [gen+1, prenlen) , 右子中序序列 for(int i = gen+1; i < prelen; i++) { preright.push_back(pre[i]); vinright.push_back(vin[i]); } //递归左右子树 root->left = reConstructBinaryTree(preleft, vinleft); root->right = reConstructBinaryTree(preright, vinright); return root; } };