m*****f 发帖数: 1243 | 1 CLRS 10.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.
no recursive...O(1) space...cannot modify tree... | d*******n 发帖数: 141 | 2 O(1)space咋弄呢……逐层遍历可以不递归
tree,
【在 m*****f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : CLRS 10.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. : no recursive...O(1) space...cannot modify tree...
| H*M 发帖数: 1268 | 3 use parent pointer
BST in CLRS usually has parent pointer
otherwise i dont think it is possible
tree,
【在 m*****f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : CLRS 10.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. : no recursive...O(1) space...cannot modify tree...
|
|