用前序和中序遍历构建二叉树
/**
* 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) {
TreeNode* tree;
tree = GetSubTree(pre,vin,0,pre.size()-1,0,vin.size()-1);
return tree;
}
TreeNode* GetSubTree(vector<int>&pre, vector<int>&vin, int pre_l,int pre_r,int in_l,int in_r)
{
if(pre_l>pre_r||in_l>in_r)
{
return NULL;
}
//中序遍历中的父节
int mid = in_l;
while(mid<=in_r&&vin[mid]!=pre[pre_l]){mid++;}
//得到左子子树的长度
int left_num = mid-in_l;
TreeNode* T = new TreeNode(pre[pre_l]);
T->left = GetSubTree(pre,vin,pre_l+1, left_num+pre_l,in_l,mid-1);
T->right = GetSubTree(pre,vin,left_num+pre_l+1,pre_r,mid+1,in_r);
return T;
}
};
