Redian新闻
>
AMEX PRG 买100的AA GIFT CARD 给报吗?
avatar
AMEX PRG 买100的AA GIFT CARD 给报吗?# Money - 海外理财
j*l
1
Given a root of a tree. The tree may be of any depth and width,
each node may have any number of child nodes.
This method should transform a tree in such a way
that each node (except probably one) would either have N or 0 children
class Node {
T data;
List> children;
}
avatar
m*g
2
DELTA 只能买50,AA 的呢?
avatar
c*p
3
遍历结点,然后变成满N叉树?
avatar
t*7
4
可以
avatar
b*0
5
层次遍历...

【在 j********l 的大作中提到】
: Given a root of a tree. The tree may be of any depth and width,
: each node may have any number of child nodes.
: This method should transform a tree in such a way
: that each node (except probably one) would either have N or 0 children
: class Node {
: T data;
: List> children;
: }

avatar
M*e
6
ua gift registry还可以吗?似乎没有今年的data point.
avatar
y*e
7
这是你今天的面试题吗。。。。
avatar
b*i
8
展开来说说?

【在 b********0 的大作中提到】
: 层次遍历...
avatar
b*i
9
不太明白,最naive的就是先用任何方法遍历一下,存在一个大list里面,
再把这个list转成个complete N叉树

【在 j********l 的大作中提到】
: Given a root of a tree. The tree may be of any depth and width,
: each node may have any number of child nodes.
: This method should transform a tree in such a way
: that each node (except probably one) would either have N or 0 children
: class Node {
: T data;
: List> children;
: }

avatar
c*e
10
我想这题主要是要看你能否有办法,边遍历,边变形,这样又快又省空间
先拆散成一堆节点,再建树当然是可行的,只是时间空间都不最优
avatar
r*g
11
这样行不
层次遍历原来的树, 每次收集N个节点放到新树
TreeNode *convertNTree(TreeNode *root, int N)
{
TreeNode *new_tree = root;
std::queue q1, q2;
std::list chd;
q1.push(root);
q2.push(root);
while(!q1.empty()){
if(chd.size() < N){
for(auto p: q1.front().children){
q1.push(p);
}
q1.front().children.resize(0);
chd.push_back(q1.front());
q1.pop();
}else{
std::swap(q2.front().children, chd);
for(auto p: q2.front().children){
q2.push(p);
}
q2.pop();
}
}
std::swap(q2.front().children, chd);
return new_tree;
}

【在 j********l 的大作中提到】
: Given a root of a tree. The tree may be of any depth and width,
: each node may have any number of child nodes.
: This method should transform a tree in such a way
: that each node (except probably one) would either have N or 0 children
: class Node {
: T data;
: List> children;
: }

avatar
p*e
12
N是code判断的
avatar
x*u
13
层次遍历, queue里面只有一层的nodes. N很大的时候, N个节点的group还没形成, 有
些点就被poll out了.
觉得就用DFS的遍历, 遍历过的点存起来, 满N了, 就生成一个新树的节点.
直到DFS遍历完老树.

【在 r*g 的大作中提到】
: 这样行不
: 层次遍历原来的树, 每次收集N个节点放到新树
: TreeNode *convertNTree(TreeNode *root, int N)
: {
: TreeNode *new_tree = root;
: std::queue q1, q2;
: std::list chd;
: q1.push(root);
: q2.push(root);
: while(!q1.empty()){

avatar
r*g
14

一直都在poll out,我放chd临时链表了
chd长度到N就swap到新树当前节点的孩子链表。
其实这是个O(n)空间solution
和naive方法没本质区别。
在不知道n的情况下建N叉完全树
若是一层一层建,空间复杂度一直在n量级

【在 x********u 的大作中提到】
: 层次遍历, queue里面只有一层的nodes. N很大的时候, N个节点的group还没形成, 有
: 些点就被poll out了.
: 觉得就用DFS的遍历, 遍历过的点存起来, 满N了, 就生成一个新树的节点.
: 直到DFS遍历完老树.

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。