[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
{1,2,3,4,#,5,6,#,7,#,#,8}返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示
[1],[1]
{1}[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
{1,2,5,3,4,6,7}
int searchArr(int *Arr, int ArrLen, int p) {
int i;
for(i=0;i<ArrLen;i++) {
if(p==Arr[i])
return i;
}
return -1;
}
struct TreeNode* reConstructBinaryTree(int* preOrder, int preOrderLen, int* vinOrder, int vinOrderLen ) {
struct TreeNode* res;
int leftTreeLen, rightTreeLen;
if(!preOrderLen)
return NULL;
res = (struct TreeNode*)malloc(sizeof(struct TreeNode));
res->val = preOrder[0];
leftTreeLen = searchArr(vinOrder, vinOrderLen, preOrder[0]);
rightTreeLen = preOrderLen-1-leftTreeLen;
res->left = reConstructBinaryTree(preOrder+1, leftTreeLen, vinOrder, leftTreeLen);
res->right = reConstructBinaryTree(preOrder+1+leftTreeLen, rightTreeLen, vinOrder+leftTreeLen+1, rightTreeLen);
return res;
} 
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param preOrder int整型一维数组
* @param preOrderLen int preOrder数组长度
* @param vinOrder int整型一维数组
* @param vinOrderLen int vinOrder数组长度
* @return TreeNode类
*/
#include <stdlib.h>
struct TreeNode* reConstructBinaryTree(int* preOrder, int preOrderLen, int* vinOrder, int vinOrderLen ) {
// write code here
if (preOrderLen == 0) {
return NULL;
}
int rootValue = *preOrder;
int index = 0;
while (vinOrder[index] != rootValue) {
index ++;
}
struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
root->val = rootValue;
root->left = reConstructBinaryTree(preOrder + 1, index, vinOrder, index);
root->right = reConstructBinaryTree(preOrder + 1 + index, preOrderLen - index - 1, vinOrder + index + 1, vinOrderLen - index - 1);
return root;
} 
struct TreeNode* reConstructBinaryTree(int* preOrder, int preOrderLen, int* vinOrder, int vinOrderLen ) {
// write code here
if (preOrderLen == 0) {
return NULL;
}
int precur = 0, vincur = 0, top = 0;
bool flag = false;
struct TreeNode* stack[2000];
struct TreeNode* root, * now;
root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = preOrder[precur++];
stack[0] = root;
while (precur < preOrderLen) {
while (stack[top]->val == vinOrder[vincur]) {
vincur++;
now = stack[top--];
flag = true;
}
struct TreeNode* temp;
temp = (struct TreeNode*)malloc(sizeof(struct TreeNode));
temp->val = preOrder[precur++];
if (flag) {
now->right = temp;
flag = false;
} else {
stack[top]->left = temp;
}
top++;
stack[top] = temp;
}
return root;
} 
void _reConstructBinaryTree(struct TreeNode** root,int* pre, int preLen, int* idx,int* vin, int l,int r,int dir)
{
if(l>r)
return;
int i = l; struct TreeNode* node;
for(i=l;i<=r;i++)
{
if(pre[*idx] == vin[i])
{
(*idx) ++;
node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if(node == NULL)
return;
node->val = vin[i];
node->left = NULL;
node->right = NULL;
if(*root == NULL)
*root = node;
else {
if(dir == 0)
(*root)->left = node;
else
(*root)->right = node;
}
break;
}
}
_reConstructBinaryTree(&node,pre,preLen,idx,vin,l,i-1,0);
_reConstructBinaryTree(&node,pre,preLen,idx,vin,i+1,r,1);
}
struct TreeNode* reConstructBinaryTree(int* pre, int preLen, int* vin, int vinLen )
{
// write code here
struct TreeNode* root = NULL;
int idx = 0;
_reConstructBinaryTree(&root,pre,preLen,&idx,vin,0,vinLen-1,-1);
return root;
} 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1); return root; } //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6} private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) { if(startPre>endPre||startIn>endIn) return null; TreeNode root=new TreeNode(pre[startPre]); for(int i=startIn;i<=endIn;i++) if(in[i]==pre[startPre]){ root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1); root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn); break; } return root; } }