给定一棵带有整数、左指针和右指针的二叉树,如何在 O(n) 时间和 O(1) 额外内存(无堆栈/队列/递归)内遍历该树?
This guy http://nandacumar.blogspot.com/2006/06/traversing-tree.html给出了一个将当前路径编码为整数的总时间不是 O(n) 的解决方案(因此适用于有限深度的树)。
我正在寻找经典的解决方案
(剧透)
对子节点中每个节点的父节点进行编码。
任何好的算法书都会有这个算法,例如在 Knuth 中(TAOCP I.2.3.1 遍历二叉树,练习 21)。但是,由于该算法会就地修改树,因此您必须使用extreme在多线程环境中要小心。
您还可以使用线程树(参见 Knuth)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)