i***h
发帖数: 12655 | 1 这个是那本算法书二叉树一节后的题
网上查了下,除非节点带对父节点的指针才行,好象作弊了(这个额外的指针就是O(n)空
间了)
有答案么?
谢谢 |
c*****t
发帖数: 1879 | 2 If the tree can be modified...
/ \ are downward arrows, * is the upward arrow, stored in either left
or right branch.
root := A
A
/ \
B C
/ \
D E
1.
A
* \
B C
/ \
D E
2.
A
* \
B C
* \
D E
3. then backup and visit E
A
* \
B C
【在 i***h 的大作中提到】
: 这个是那本算法书二叉树一节后的题
: 网上查了下,除非节点带对父节点的指针才行,好象作弊了(这个额外的指针就是O(n)空
: 间了)
: 有答案么?
: 谢谢
|
i***h
发帖数: 12655 | 3 你问到点子上了
要求是不能
[Cormen习题11.4-5] O(n) time, non-recursive, constant extra space, do not
modify the tree (even temporarily)
很刁难人啊
【在 c*****t 的大作中提到】
: If the tree can be modified...
: / \ are downward arrows, * is the upward arrow, stored in either left
: or right branch.
: root := A
: A
: / \
: B C
: / \
: D E
: 1.
|
c*****t
发帖数: 1879 | 4 那么题目出错了 :)
100% 可以肯定。
【在 i***h 的大作中提到】
: 你问到点子上了
: 要求是不能
: [Cormen习题11.4-5] O(n) time, non-recursive, constant extra space, do not
: modify the tree (even temporarily)
: 很刁难人啊
|
l******u
发帖数: 1174 | 5 你肯定你看见了整个题目了?
就这个?
lz把原题找出来我们再下结论吧. |
i***h
发帖数: 12655 | 6 Introduction to Algorithms
1990 MIT Press
Page 216
11.4-5 *
Write an O(n)-time nonrecursive procedure that, given an n-node binary tree,
prints out the key of each node. Use no more than constant extra space
outside of the tree itself and do not modify the tree, even temporarily,
during the procedure. |
n******t
发帖数: 4406 | 7 哈哈，同学你被晃点了，CLRS那本书里面的binrary tree每个节点是带了
指向parent节点的指针的。
【在 i***h 的大作中提到】
: 这个是那本算法书二叉树一节后的题
: 网上查了下,除非节点带对父节点的指针才行,好象作弊了(这个额外的指针就是O(n)空
: 间了)
: 有答案么?
: 谢谢
|
l******u
发帖数: 1174 | 8 The problem doesn't specify how the binary tree is stored, and whether the
traversal has to be in certain order. These are the two areas you can
expand on. If the solution has to work for any binary tree implementation
and any traversal order, I think it simply does not exist.
You can certainly store a binary tree in a way so that it can be traversed
in O(n) time + O(1) space. Parent pointer is one simply way. Storing in a
continuous array is another. Or you can use sibling pointers. Etc.
In
【在 i***h 的大作中提到】
: Introduction to Algorithms
: 1990 MIT Press
: Page 216
: 11.4-5 *
: Write an O(n)-time nonrecursive procedure that, given an n-node binary tree,
: prints out the key of each node. Use no more than constant extra space
: outside of the tree itself and do not modify the tree, even temporarily,
: during the procedure.
|
i***h
发帖数: 12655 | 9 一语惊醒梦中人
原来不是我傻
而是我傻透了
多谢大家的讨论和指点
【在 n******t 的大作中提到】
: 哈哈，同学你被晃点了，CLRS那本书里面的binrary tree每个节点是带了
: 指向parent节点的指针的。
|
i***h
发帖数: 12655 | 10 Thanx
binary
node.
【在 l******u 的大作中提到】
: The problem doesn't specify how the binary tree is stored, and whether the
: traversal has to be in certain order. These are the two areas you can
: expand on. If the solution has to work for any binary tree implementation
: and any traversal order, I think it simply does not exist.
: You can certainly store a binary tree in a way so that it can be traversed
: in O(n) time + O(1) space. Parent pointer is one simply way. Storing in a
: continuous array is another. Or you can use sibling pointers. Etc.
: In
|
