e****d
发帖数: 333 | |
d***a
发帖数: 13752 | 2 有计算复杂度的要求吗？
【在 e****d 的大作中提到】
: 百思不得其解，等大师们指教。
|
e****d
发帖数: 333 | |
a****l
发帖数: 8211 | 4 节省空间的必然浪费时间。常量的空间就需要平方的时间。
【在 e****d 的大作中提到】
: 百思不得其解，等大师们指教。
|
w***g
发帖数: 5958 | 5 得构造合适的数据结构. 每个节点两个指针只想儿子节点那种明显不行.
【在 e****d 的大作中提到】
: 百思不得其解，等大师们指教。
|
c*********e
发帖数: 16335 | 6 按层遍历二叉树,无非就是把每个节点当作数组arr里的一個元素，一個index对应一個
节点。比如根节点index=０ (2的０次方 减 1）,第二层的最左边那个节点index=1 (2
的一次方 减 1）,第三层的最左边那个节点的index=3 (2的二次方 减 1 ）第四层的最
左边那个节点的index=7 (2的三次方 减 1）,etc.
所以，第一层就是arr[0]; (最左边节点index 0 为 2的０次方 减 1）
第二层就是arr[1]，arr[2]; (最左边节点index 1 为 2的1次方 减 1，最右边节点
index 2 为 下一层第一個节点的index（值为3） 减 1）
第三层就是arr[3]，arr[4],arr[5],arr[6]; (最左边节点index 3 为 2的2次方 减 1
，最右边节点index 6 为 下一层第一個节点的index（值为7） 减 1）
etc.
这样就可以按层遍历了。
【在 e****d 的大作中提到】
: 百思不得其解，等大师们指教。
|
c*********e
发帖数: 16335 | 7 多加几个指针，存当前的层的第一個节点的指针的值和上2层的第一個节点的指针的值。
【在 e****d 的大作中提到】
: 百思不得其解，等大师们指教。
|
r*****e
发帖数: 792 | 8 A linear time constant space solution:
The key idea is to use DFS to visit the tree in BFS fashion.
void visit(Node *root, int height) {
if (height==1) cout<< root->value;
else {
if (root->left) visit(root->left, height-1);
if (root->right) visit(root->right, height-1);
}
}
void visitBFS(Node *root) {
if (!root) return;
int heightOfTree = getHeight(root);//will not define here
for (int h=1; h<=heightOfTree; ++h) {
visit(root, h);
}
}
【在 e****d 的大作中提到】
: 百思不得其解，等大师们指教。
|
Y**G
发帖数: 1089 | 9 这一递归，用的空间就不是常数O(1)了
【在 r*****e 的大作中提到】
: A linear time constant space solution:
: The key idea is to use DFS to visit the tree in BFS fashion.
: void visit(Node *root, int height) {
: if (height==1) cout<< root->value;
: else {
: if (root->left) visit(root->left, height-1);
: if (root->right) visit(root->right, height-1);
: }
: }
: void visitBFS(Node *root) {
|
s*****n
发帖数: 5488 | 10 如果可以破坏树的结构是可以的，思路是把二叉树，转换为兄弟树。
第一遍转化为兄弟树后，则rightchild指针省下来了，那么值想
p->leftchild->sibling->next = p->next->leftchild, 这样就构成了一张linkedlist
per level.然后for level, print linkedlist.
我估计最后兄弟树还可以恢复为二叉树。
不过这个方法算是很闲的蛋疼了。
【在 e****d 的大作中提到】
: 百思不得其解，等大师们指教。
|
