y*e
3 楼
是BST嘛?假设是BST。
6
/ \
4 8
/ \ / \
1 5 7 9
inorder是 1 4 5 6 7 8 9
levelorder是 6 4 8 1 5 7 9
6
/ \
4 8
/ / \
1 7 9
inorder是 1 4 6 7 8 9
levelorder是 6 4 8 1 7 9
注意到,在 levelorder 中, INDEX (parent) < INDEX (node)。
解法思路如下:
1、取 levelorder 的第一个,作为 root。在 inorder 里面,小于 root 的值,是为
left sub tree。在 inorder 里面,大于root 的值,是为 right sub tree。
2、在 levelorder 里面找寻第一个值 n,使得 n < root && INDEX(n) >
INDEX(root)
【在 K******g 的大作中提到】
: 请问有谁知道这题的思路?多谢了
g*d
5 楼
好像是从本版抄的.
node * restore(int pre[], int in[], int N)
{
if (!N) return NULL;
int * it = std::lower_bound(in, in + N, *pre);
assert(it != in + N && !(*pre < *it));
int index = it - in;
node * root = new node(*pre);
root->left = restore(pre + 1, in, index);
root->right = restore(pre + index + 1, in + index + 1, N - index - 1);
return root;
}
node * restore(int pre[], int in[], int N)
{
if (!N) return NULL;
int * it = std::lower_bound(in, in + N, *pre);
assert(it != in + N && !(*pre < *it));
int index = it - in;
node * root = new node(*pre);
root->left = restore(pre + 1, in, index);
root->right = restore(pre + index + 1, in + index + 1, N - index - 1);
return root;
}
c*w
6 楼
仅仅靠Index(Parent) 子树的根啊?
比如:
int inorderSeq[]= {2,4,9,8,3,1,6,7,5};
int levorderSeq[]={1,2,5,3,6,4,7,8,9};
When you go to the first element of level order 1, it is the root, 1
separate the in order seq into two parts. The left part is its left subtree
[2,4,9,8,3], the right part is its right subtree[6,7,5]. The program goes to
the left subtree, we need find which one is the root of left subtree.
The root of left subtree is the one with the minimum level
【在 y*********e 的大作中提到】
:
: 是BST嘛?假设是BST。
: 6
: / \
: 4 8
: / \ / \
: 1 5 7 9
: inorder是 1 4 5 6 7 8 9
: levelorder是 6 4 8 1 5 7 9
: 6
比如:
int inorderSeq[]= {2,4,9,8,3,1,6,7,5};
int levorderSeq[]={1,2,5,3,6,4,7,8,9};
When you go to the first element of level order 1, it is the root, 1
separate the in order seq into two parts. The left part is its left subtree
[2,4,9,8,3], the right part is its right subtree[6,7,5]. The program goes to
the left subtree, we need find which one is the root of left subtree.
The root of left subtree is the one with the minimum level
【在 y*********e 的大作中提到】
:
: 是BST嘛?假设是BST。
: 6
: / \
: 4 8
: / \ / \
: 1 5 7 9
: inorder是 1 4 5 6 7 8 9
: levelorder是 6 4 8 1 5 7 9
: 6
j*l
7 楼
看题不仔细~
不是pre + in
【在 g******d 的大作中提到】
: 好像是从本版抄的.
: node * restore(int pre[], int in[], int N)
: {
: if (!N) return NULL;
: int * it = std::lower_bound(in, in + N, *pre);
: assert(it != in + N && !(*pre < *it));
: int index = it - in;
: node * root = new node(*pre);
: root->left = restore(pre + 1, in, index);
: root->right = restore(pre + index + 1, in + index + 1, N - index - 1);
不是pre + in
【在 g******d 的大作中提到】
: 好像是从本版抄的.
: node * restore(int pre[], int in[], int N)
: {
: if (!N) return NULL;
: int * it = std::lower_bound(in, in + N, *pre);
: assert(it != in + N && !(*pre < *it));
: int index = it - in;
: node * root = new node(*pre);
: root->left = restore(pre + 1, in, index);
: root->right = restore(pre + index + 1, in + index + 1, N - index - 1);
相关阅读
好猫应该创建一个eastside面试俱乐部帮忙看个题SQL 面试的问题一般都会问啥?有在Honeywell的吗phd码工的困惑请教,给f1的offer letter里一般会写办H1和绿卡的时间表等细感恩节感谢Job Hunting版,祝愿今年明年找工作的人顺利拿到大奥佛!!有人做过Caliper Assessment 吗?(包子答谢)弱问quantcast这家公司怎样cegedim 这个公司怎么样湾区码农一年都存多少钱啊硅谷的公司401k match都给的很低吗Thanksgiving包子请问这道behavior题想考察什么呀leetcode 4sum N^3解法有时Time Limit Exceeded有时又能通过MS intern转正难吗onsite后没动静啊有哪些公司可以在入职前给relocation fee?请问有人有pinterest phone interview 面经吗?大家一般怎么了解一个小公司