binary-tree - 按升序打印两个二叉树的节点

Question

给定两个二叉搜索树，以时间复杂度O(n)和空间复杂度O(1)升序打印节点

这些树无法修改。仅允许遍历。

我面临的问题是O(1)空间解决方案。如果没有此限制，则可以轻松解决。

Answer 1

可以在空间O(1)中完成此操作的唯一方法是节点是否知道其父节点。
否则，除非有其他帮助，否则您甚至无法遍历树。
但是，有了这个约束，它又很容易又回到了树遍历，但是没有递归。棘手的部分可能是知道从节点到其父节点(p)时来自哪个树路径，并且无法存储此信息，因为这将需要O(log N)空间。
但是，您知道输出的最后一个值。如果小于p中的一个，则向右移动，否则转到p的父级。