剑指offer,重建数组
先上代码
class Solution { public: TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { vector<int> left_pre ,left_vin ,right_pre ,right_vin; int length=vin.size(); if(length==0) return NULL; TreeNode *root=new TreeNode(pre[0]); int roo=0; for(int i=0;i<length;i++) { if(vin[i]==pre[0]) { roo=i; break; } } for(int i=0;i<roo;i++)//左支 { left_vin.push_back(vin[i]);//把根节点之前的归到这个数组 left_pre.push_back(pre[i+1]); } for(int i=roo+1;i<length;i++)//右支 { right_vin.push_back(vin[i]);//把根节点之前的归到这个数组 right_pre.push_back(pre[i]); } root->left=reConstructBinaryTree(left_pre,left_vin); root->right=reConstructBinaryTree(right_pre,right_vin); return root;
2.思路分析:
1.在中序列表中找到根节点
2.把根节点左右子树分成两列表
3.左子树也分一个前序和中序数组
4.右子树也分一个前序和中序数组
(返回根节点)
5.根节点的左节点递归1-4,右节点同理
6.返回根节点