h*****g
发帖数: 312 | 1 7
/ \
8 9
\ / \
5 4 6
inorder: 857496
BFS: 789645
如何 重构这个二叉树，然后求树的宽度（哪一层node最多？） | l**********1
发帖数: 415 | 2 写了个练手，求牛人指正
public static TreeNode rebuild(int[] inorder,int[] bfs,int bfsl,int bfsh,int
inorderl, inorderh){
//base case
if(bsfl>=bfsh||inorderl>inorderh) return null;
TreeNode root=new TreeNode();
root.value=bfs[bfsl];
//find the index of root value in inorder array
int cutoff=findCut(inorder,inorderl,inorderh,bfs[bfsl]);
//build the tree recursively
root.right=rebuild(inorder,bfs,bfsl+1,bfsh,inorderl,cutoff-1);
root.left=rebuild(inorder,bfs,bfsl+2,bfsh,cutoff+1,inorderh);
return root;
}
public static int findCut(int[] array, int l, int h, int x){
for(int i=0;i<=h,i++){
if(array[i]==x)
return i;
}
return -1;
}
//API call
//rebuild(inorder,bfs,0,bfs.length,0,inorder.length-1); | s******n
发帖数: 3946 | 3 楼上完全错误，不能用root分两段，这办法只适合preorder+inorder | l**********1
发帖数: 415 | 4 请问为什么不能用root分两段？inorder不是所有左子树全在左边，右子树全在右边么
？ | s******n
发帖数: 3946 | 5 BFS没法一刀切割成左右树
【在 l**********1 的大作中提到】
: 请问为什么不能用root分两段？inorder不是所有左子树全在左边，右子树全在右边么
: ？
| h*****y
发帖数: 218 | 6 题目没有看清楚
是BFS and inorder
【在 l**********1 的大作中提到】
: 请问为什么不能用root分两段？inorder不是所有左子树全在左边，右子树全在右边么
: ？
| c******w
发帖数: 1108 | 7 preorder+inorder 和 BFS+inorder没有本质区别
【在 s******n 的大作中提到】
: 楼上完全错误，不能用root分两段，这办法只适合preorder+inorder
| e*****e
发帖数: 1275 | 8 我觉得这题得用queue.
随便乱写了点，运行没有问题：
typedef struct bfs_binary_tree_info
{
binary_tree * parent;
//true for left child, false for right child
bool left_flag;
int * inorder;
int m;
int BFS_index;
}bfs_binary_tree_info;
binary_tree * build_binary_tree_from_inorder_BFS2 ( int inorder[], int m,
int BFS[], int BFS_index )
{
//verify input, make sure they are all valid
int root = BFS[BFS_index];
int root_in_index = -1;
queue tree_queue;
int prev_lvl_count = 0;
int cur_lvl_count = 0;
int child_count = 0;
binary_tree * return_tree = NULL;
bfs_binary_tree_info * tmp_info;
bfs_binary_tree_info * info = (bfs_binary_tree_info * )malloc (sizeof (
bfs_binary_tree_info ));
info->parent = NULL;
info->left_flag = true;///we dont care since parent is NULL, this is
root
info->m = m;
info->inorder = inorder;
info->BFS_index =BFS_index;
bfs_binary_tree_info * end = (bfs_binary_tree_info * )malloc (sizeof (
bfs_binary_tree_info ));
end->parent = NULL;
end->left_flag = true;///we dont care since parent is NULL, this is root
end->m = m;
end->inorder = NULL;
end->BFS_index =BFS_index;
tree_queue.push (info);
tree_queue.push (end);
while (!tree_queue.empty ())
{
tmp_info = tree_queue.front ();
tree_queue.pop ();
if (tmp_info == end)
{
if (!tree_queue.empty ())
{
tree_queue.push (end);
prev_lvl_count += cur_lvl_count;
cur_lvl_count = 0;
child_count = 0;
}
else
{
//eend of it
break;
}
}
else
{
binary_tree * node = (binary_tree *) malloc (sizeof (binary_tree
));
cur_lvl_count++;
node->data = BFS[tmp_info->BFS_index + prev_lvl_count];
node->left = NULL;
node->right = NULL;
if (tmp_info->parent == NULL)
{
return_tree = node;
}
else
{
if (tmp_info->left_flag)
tmp_info->parent->left = node;
else
tmp_info->parent->right = node;
}
//now find the root from inorder
for (int i = 0; i < tmp_info->m; i++)
{
if (tmp_info->inorder[i]==node->data)
root_in_index = i;
}
if (root_in_index != 0 )
{
bfs_binary_tree_info * new_info = (bfs_binary_tree_info * )
malloc (sizeof (bfs_binary_tree_info ));
new_info->parent = node;
new_info->left_flag = true;///we dont care since parent is
NULL, this is root
new_info->m = root_in_index;
new_info->inorder = tmp_info->inorder;
new_info->BFS_index = child_count;
tree_queue.push (new_info);
child_count++;
//do have left child
//node->left = build_binary_tree_from_inorder_BFS (inorder,
root_in_index, BFS, ++BFS_index);
}
if (root_in_index != tmp_info->m -1 )
{
//do have right child
bfs_binary_tree_info * new_info = (bfs_binary_tree_info * )
malloc (sizeof (bfs_binary_tree_info ));
new_info->parent = node;
new_info->left_flag = false;///we dont care since parent is
NULL, this is root
new_info->inorder = tmp_info->inorder + root_in_index + 1;
new_info->m = tmp_info->m - root_in_index - 1;
new_info->BFS_index =child_count;
child_count++;
tree_queue.push (new_info);
}
}
}
//now from 0 to root_in_index is left side
//from root_in_index to m is right side
return return_tree;
}
int inorder[]= {8,5,7,4,9,6};
int BFS[]= {7,8,9,5,4,6};
binary_tree * tree = build_binary_tree_from_inorder_BFS2 (inorder, 6, BFS, 0
); | n******n
发帖数: 49 | | k*******r
发帖数: 355 | 10 虽然一个子树在BFS 序列中会不连续，但我觉得这道题还是可以模拟preorder+inorder
用递归做，唯一要额外注意的就是要把不连续的BFS串抽出来拼成连续串（以便这个连
续串对应一个子树）
code写起来也不麻烦，十几行吧，请高手指正
struct node{node * l,r; int id;}
node * f(int b[], int i[], int len){
if (len==0){return NULL}
node * h=new node; h->id=b[0]; h->l=NULL; h->r=NULL;
if (len==1){ return h;}
int k=findhead(b[0], i); map m;
int *newi=new int[k]; for (int j=0; j
int *newb=new int[k]; for (int j=0; j
h->l=f(newb, newi,k);
int *newi2=new int[len-k-1]; for (int j=k+1; j
int *newb2=new int[len-k-1]; for (int j=0; j
h->r=f(newb2, newi2,len-k-1);
return h;
} | p*****2
发帖数: 21240 | 11 看了看，感觉应该可以分两段。
BFS 可以看出7是root
indorder可以看出85是左树，496是右树
BFS又可以看出，8是左树的根，9是右树的根
7
/ \
8 9
\ / \
5 4 6
inorder: 857496
BFS: 789546 | p****n
发帖数: 148 | 12 有虫吧
有输入错
＋1＋2也不对巴
要不要在楼主的例子上跑一跑？
int
【在 l**********1 的大作中提到】
: 写了个练手，求牛人指正
: public static TreeNode rebuild(int[] inorder,int[] bfs,int bfsl,int bfsh,int
: inorderl, inorderh){
: //base case
: if(bsfl>=bfsh||inorderl>inorderh) return null;
: TreeNode root=new TreeNode();
: root.value=bfs[bfsl];
: //find the index of root value in inorder array
: int cutoff=findCut(inorder,inorderl,inorderh,bfs[bfsl]);
: //build the tree recursively
|
|
