是否有可能在O(1)辅助空间中迭代二叉树(没有使用堆栈,队列等),或者这被证明是不可能的？如果有可能,怎么办呢？
编辑:如果有关于父节点的指针很有趣并且我不知道这可以做到,那么我得到的关于这可能的响应是可能的,但是根据你如何看待它,可以是O(n)辅助空间.此外,在我的实际用例中,没有指向父节点的指针.从现在开始,请在回答时假设这一点.
language-agnostic algorithm tree binary-tree memory-management
我正在读一本名为" 算法简介 "的书.我想很多人都知道.我刚刚碰到一个看似相当困难的问题:
编写一个O(n)-time非递归过程,给定一个n节点二叉树,打印出每个节点的密钥.在树本身之外使用不超过恒定的额外空间,并且在过程中不要修改树,即使是暂时的.
我看到还有另外一个问题:如何在没有额外内存的情况下在O(n)时间遍历二叉树,但主要区别在于我无法修改树.我正在考虑使用一些访问过的标志,但我还没有提出正确的解决方案.这可能是我看不到的明显的东西.你会如何设计一个解决这个问题的算法？即使是对答案的一些指示也会受到赞赏.