h****e
发帖数: 928 | 1 一道常见的面试题是print binary tree level by level。
现在有一道反过来的题目，就是给定每一层的结点，构造出
BST来。例如给出以下的vector >：
5
4 8
2 7 9
3 10
要求构造出相应的BST:
5
4 8
2 7 9
3 10
我的想法是可以把输入看作是一个一维的vector，一个个结点
地插入，这样可以得到相应的BST，复杂度是O(NlogN)吧。
问题是这种做法没有利用给出的结点已经分好层的特点，每次都从
根节点开始，似乎不是最有效的。
请问还有更好的办法吗？ |
p*****2
发帖数: 21240 | |
h****e
发帖数: 928 | 3 二爷真的是recursion修炼到一字师的地步了。:)
Recursion怎么个做法？
【在 p*****2 的大作中提到】
: recursion
|
n****n
发帖数: 117 | 4 merge sorted的list啊
【在 h****e 的大作中提到】
: 一道常见的面试题是print binary tree level by level。
: 现在有一道反过来的题目，就是给定每一层的结点，构造出
: BST来。例如给出以下的vector >：
: 5
: 4 8
: 2 7 9
: 3 10
: 要求构造出相应的BST:
: 5
: 4 8
|
h****e
发帖数: 928 | 5 这个，不行吧，最后生成的是2->3->4->5->...，不是树吧。
【在 n****n 的大作中提到】
: merge sorted的list啊
|
p*****2
发帖数: 21240 | 6
5
4 8
2 7 9
3 10
我的想法是这样。
5是root
4是left tree
8是right tree
到4的时候数值范围是 Integer.MinValue - 5
左tree的范围 Integer,MinValue - 4
右tree的范围 4-5
这样你就知道2是左tree，这样recursion就可以了。
【在 h****e 的大作中提到】
: 二爷真的是recursion修炼到一字师的地步了。:)
: Recursion怎么个做法？
|
h****e
发帖数: 928 | 7 这样你是不是需要maintain每一层的所有的结点呢？可能空间要求就
上去了吧。
我的做法如下。这样写的好处是面试时可以写得出来，但是就是不知道
复杂度是不是最优了：
// it is also easy to write an iterative insertion function
void insert_node(Node*& root, int v) {
if (root==0) {
root = new Node(v);
return;
}
if (root->data>v) {
insert_node(root->left, v);
} else {
insert_node(root->right, v);
}
}
Node* construct_tree(vector > nodes)
{
Node* root = 0;
for (int i=0; i
const vector& numbers = nodes[i];
for (int j=0; j
insert_node(root, numbers[j]);
}
}
return root;
}
【在 p*****2 的大作中提到】
:
: 5
: 4 8
: 2 7 9
: 3 10
: 我的想法是这样。
: 5是root
: 4是left tree
: 8是right tree
: 到4的时候数值范围是 Integer.MinValue - 5
|
p*****2
发帖数: 21240 | 8
怎么maintain？你是说stack的空间？如果不用recursion, BFS也可以。但是时间肯定
不能超过O(n)吧。
【在 h****e 的大作中提到】
: 这样你是不是需要maintain每一层的所有的结点呢？可能空间要求就
: 上去了吧。
: 我的做法如下。这样写的好处是面试时可以写得出来，但是就是不知道
: 复杂度是不是最优了：
: // it is also easy to write an iterative insertion function
: void insert_node(Node*& root, int v) {
: if (root==0) {
: root = new Node(v);
: return;
: }
|
h****e
发帖数: 928 | 9 二爷有时间的话发一段code吧，我不理解如何在知道4,8以及它们的
子树的取值范围以后处理2,7,9的。
【在 p*****2 的大作中提到】
:
: 怎么maintain？你是说stack的空间？如果不用recursion, BFS也可以。但是时间肯定
: 不能超过O(n)吧。
|
w****x
发帖数: 2483 | 10 top down recursion, recursion下来的函数要传递range |
|
|
p*****2
发帖数: 21240 | 11 写了一个BFS的。
class Node
{
int value;
Node left;
Node right;
public Node(int v)
{
value = v;
}
}
class Ele
{
int min;
int max;
Node ref;
public Ele(int _min, int _max, Node _ref)
{
min = _min;
max = _max;
ref = _ref;
}
}
Node convert(ArrayList> tree)
{
Queue queue = new LinkedList();
Node root = new Node(tree.get(0).get(0));
queue.add(new Ele(Integer.MIN_VALUE, Integer.MAX_VALUE, root));
int level = 1;
int count = 1;
int i = 0;
while (!queue.isEmpty() && level < tree.size())
{
ArrayList al = tree.get(level);
Ele ele = queue.poll();
if (i < al.size() && al.get(i) >= ele.min
&& al.get(i) <= ele.ref.value)
{
Node left = new Node(al.get(i));
ele.ref.left = left;
queue.add(new Ele(ele.min, ele.ref.value, left));
i++;
}
if (i < al.size() && al.get(i) <= ele.max
&& al.get(i) > ele.ref.value)
{
Node right = new Node(al.get(i));
ele.ref.right = right;
queue.add(new Ele(ele.ref.value, ele.max, right));
i++;
}
count--;
if (count == 0)
{
level++;
count = queue.size();
i = 0;
}
}
return root;
} |
f****0
发帖数: 151 | 12
我也觉得是，然后判断每个range只能放一个下一层的元素，如果一个range能包含多于
一个的下一层元素，或者是某个元素无法放入紧接着的range，都返回错误
【在 w****x 的大作中提到】
: top down recursion, recursion下来的函数要传递range
|
w****x
发帖数: 2483 | 13
恩, recursion前后要还原状态, 用掉的node从vector里erase, recursion返回后再插
入, 没时间写, 以后再看
【在 f****0 的大作中提到】
:
: 我也觉得是，然后判断每个range只能放一个下一层的元素，如果一个range能包含多于
: 一个的下一层元素，或者是某个元素无法放入紧接着的range，都返回错误
|
C***U
发帖数: 2406 | 14 只要O(n)就可以了
因为你每次插入一层只需要检查一遍上一层的数字大小就能把下一层的插入
那么就是把所有的节点都走一边 就是O(n)
【在 h****e 的大作中提到】
: 一道常见的面试题是print binary tree level by level。
: 现在有一道反过来的题目，就是给定每一层的结点，构造出
: BST来。例如给出以下的vector >：
: 5
: 4 8
: 2 7 9
: 3 10
: 要求构造出相应的BST:
: 5
: 4 8
|
d**e
发帖数: 6098 | 15 能不能看作是insert a value into a bst?限制的条件是它所在input的level要跟插入
后的level一致，否则throw exception.
【在 h****e 的大作中提到】
: 一道常见的面试题是print binary tree level by level。
: 现在有一道反过来的题目，就是给定每一层的结点，构造出
: BST来。例如给出以下的vector >：
: 5
: 4 8
: 2 7 9
: 3 10
: 要求构造出相应的BST:
: 5
: 4 8
|
r*****e
发帖数: 792 | 16 每一层的数字应该是递增的，这样找同一层的就容易了。
但是好像还得存上一层的节点和root的值，否则插入时
不好判断放在哪。怎么让这块更优化还没想出好办法。
【在 h****e 的大作中提到】
: 一道常见的面试题是print binary tree level by level。
: 现在有一道反过来的题目，就是给定每一层的结点，构造出
: BST来。例如给出以下的vector >：
: 5
: 4 8
: 2 7 9
: 3 10
: 要求构造出相应的BST:
: 5
: 4 8
|
