j********l
发帖数: 325 | 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;
} |
c****p
发帖数: 6474 | |
b********0
发帖数: 62 | 3 层次遍历...
【在 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;
: }
|
y*****e
发帖数: 712 | |
b******i
发帖数: 914 | 5 展开来说说？
【在 b********0 的大作中提到】
: 层次遍历...
|
b******i
发帖数: 914 | 6 不太明白，最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;
: }
|
c*******e
发帖数: 373 | 7 我想这题主要是要看你能否有办法，边遍历，边变形，这样又快又省空间
先拆散成一堆节点，再建树当然是可行的，只是时间空间都不最优 |
r*g
发帖数: 186 | 8 这样行不
层次遍历原来的树, 每次收集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;
: }
|
p******e
发帖数: 14 | |
x********u
发帖数: 1150 | 10 层次遍历, 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()){
|
r*g
发帖数: 186 | 11
一直都在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遍历完老树.
|
