i*e
2 楼
你意思是从文件读取树，用 inorder 来重建树对吧？
【在 K******g 的大作中提到】
: 请问有谁知道这题的思路？多谢了
【在 K******g 的大作中提到】
: 请问有谁知道这题的思路？多谢了
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 的大作中提到】
: 请问有谁知道这题的思路？多谢了
K*g
4 楼
Got it. 多谢了！
【在 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
【在 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
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);
K*g
8 楼
这个解答好像有问题，试试level>3的tree，就不对了
【在 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
【在 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
相关阅读
大公司女码农能干到退休吗？那个MrSingleton和Google到底有什么仇什么怨apple on-site后这长时间没消息是不是该move on了啊Groupon电面Sign on bonus 赔偿问题G家HC过了，求team match请问 Non-Compete Agreement 的问题求问有谁有apple的map组的面经么box真的要ipo了IBM TCAD engineer 求内推一个非常努力找工作的小留的充实的一天Opening: Data Analyst@Maryland (转载)面到reverse words in string资本主义是现在猥琐男遇到的万恶的根源 (转载)年终涨薪水半年前我就劝大家去spaceX没人听OPT期间换工作，能继续在原公司作contractor吗？OPT start date 打印错了，怎么办？看到一个opening，写简历的时候是超job duty靠拢还是朝着requirement靠拢请教有人对personal banker了解的吗