题解 | #重建二叉树#

class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
// 先序遍历的首个节点为根节点
// 在中序遍历中找到根节点的位置,左侧为左子树;右侧为右子树
// 将先序遍历和中序遍历的左右子树存到数组中
// 递归左右子树,递归出口为中序遍历数组为空
int len = vin.size();
if( !len )
return NULL;
vector<int> preLeft,preRight,vinLeft,vinRight;
TreeNode* root = new TreeNode(pre[0]);
int Index = 0;
for( int i = 0; i < len ; i++ ){
if( vin[i] == pre[0] ){
Index = i;
break;
}
}
// 左子树和右子树 填充
for( int i = 0; i < Index; i++ ){
preLeft.push_back(pre[i+1]);//pre从第二个开始放入
vinLeft.push_back(vin[i]);
}
for( int i = Index+1; i < len; i++ ){
preRight.push_back(pre[i]);//pre从第二个开始放入
vinRight.push_back(vin[i]);
}
root->left = reConstructBinaryTree( preLeft, vinLeft );
root->right = reConstructBinaryTree( preRight, vinRight );
return root;
}
};</int></int></int>