想问一下关于O(1) Space遍历二叉树的问题

今天面试的题目原题是
假设在我们的内存空间中已经有了一个二叉树，我们知道他的根节点。我们需要遍历这棵树来删除它的每个节点。
假设这个树已经占有了非常大的空间，辅助空间很少。
而且我们需要每次删除是从上向下删除。

然后我理解的就是需要O(1)空间的BFS。后来跟面试官也确认了第二点就是要求O1space，但是从上向下删除这点没有更多的clarification。关于删除这个地方我理解的其实就是print也可以，因为面试官开始说了句就call一下删除就行，所以应该不重要。

我开始的思路就是Morris Traversal，这个我也是没有很熟，但是起码有些题见到过。使用prev节点进行遍历当到叶子节点就用prev在去找另一方向的节点，但是面试官提出了这个方法你不能保证每次都是从上向下遍历。

于是我就卡住了。面完了我google了半天也没发现如何O1 bfs。。。

面试官给了我很多提示，比如说辅助空间很少，我们是不是可以利用现有的空间？说再往下说就要都告诉我了，但是我还是没琢磨出来
最后面试官给了我两分钟思考，我在那碎碎念，是不是可以用链表。两分钟到了面试官问我有没有什么思路，我说还是没啥。然后他说了句你刚刚不是有说过链表，就是如何把树变成链表要考虑一下。我就想链表不还是On的吗？不懂得地方还是如何O1遍历啊 T T

问了问朋友也都没太多思路，看看地里大神有没有更多的思路，谢谢了！



补充内容 (2021-11-12 08:40 +8:00):
补充一下，在我的小本本上找到了类似的原题：利口妖妖似（我居然做过的。。。），解法1/2都是On空间，第三种解法应该就是本体的答案了，只不过面试官的问法非常独特，而且当时做的时候应该也没注意第三种O1的解法。
之前我也吃过这样一次亏，面试的时候一道做过的题上来问On的解法秒掉，之后follow up O1的就卡了半天。这次更是直接问O1方法了。。。大家刷题的时候还是要把每个解法都看一遍吼

Amorw 发表于 2021-11-9 20:57
lc的一道medium题，我在面某中厂的时候也遇到了，因为做过写出来了。其实很简单，三个pointer，用上一层的p ...

你说的这个是 摇姚遛。

但是讲道理，按照楼主说的给了一个二叉树，O1空间的话，怎么把tree node变成带next的新node…

要么楼主没说全，要么按照楼主现在的说法，不可能O1空间啊。

补充内容 (2021-11-10 15:08 +8:00):
想了想，感觉需要根面试官澄清一下需求。

1. 如果从上往下删除，表示的是严格按照层的顺序，先删第一层，再删第二层。我觉得O1空间是做不到的。
2. 如果从上往下删除，表示的，父节点一定要在子节点之前删除，那么O1空间是可以的。比如我们有一个这样的树：1，2，3，4，5  先删父节点后删子节点删除的顺序可以是1，2，4，3，5. 可以看出来这个顺序保证了父亲节点在子节点之前删除，但是层的顺序没有保证。

结合面试官也提了一嘴变成链表，我觉很大可能是第2点那样。就相当于是把二叉树变成了一个链表，具体过程是，每次先把当前节点的右孩子挪到左孩子的最下面去，然后删除当前节点，再依此继续处理左孩子。

//pseudo code
TreeNode cur = root;
while(cur != null) {
  if(cur.right != null) {
    moveRightChildToLeftChildBottom(cur);
  }
  TreeNode tmp = cur.left;
  delete(cur); // call the method to delete cur
  cur = tmp; // go ahead to process left child
}


补充内容 (2021-11-10 15:10 +8:00):
这里把tree变成linkedlist并没有占用额外的空间，因为直接把tree里面的left当场linkedlist的next来用了。
所以空间复杂度是满足O1的

recursion的话，stack的空间也不能算吗？

lc的一道medium题，我在面某中厂的时候也遇到了，因为做过写出来了。其实很简单，三个pointer，用上一层的pointer带动，把第二层的node遍历且连成一个链表。过程中，用第二个pointer record第二层的第一个节点。用第三个pointer参与遍历第二层。遍历就等于删除，打印。直到遍历完成。这道题不难，比较经典。

补充内容 (2021-11-10 13:00 +08:00):
node要加一个next节点。

这么卷，要我就直接换一家

删除节点是把每个遇到的节点设成bill?

Morris traversal。
面试之前没见过，现场打死也写不出来
cur = root找到left child的right most node，然后把这个node的right child改成cur，cur=cur.left。如果left child 的right most node 的right child已经是root，把它改为none， pirnt out root， cur=cur.right

补充内容 (2021-11-10 15:30 +08:00):
话说回来，很多tree的traversal的经典题，在leetcode的讨论里都提到了Morris Traversal。
这告诉我们虽然经典题自己做出来了，但是还是要看看评论区有没有更优解。

是不是没有利用这个提示

1. 面试官给了我很多提示，比如说辅助空间很少，我们是不是可以利用现有的空间

复制代码

删除的第一个节点可以作为我们的辅助空间。
用所有删除的节点制造一个链表，类似于如果你本来要用O（H）空间解决方案的栈
这样我们O（1）实现了从上到下的删除。


补充内容 (2021-11-11 04:49 +8:00):
注意一个现象，对于一个满二叉树来说，假如删除了三层，则删除了7个节点，下一步最多要删除8个节点。所以已经删除的7个节点排好队。外加一个多余的是可以承受的下的。

补充内容 (2021-11-11 05:05 +8:00):
我可以保证O（N）删除，O（1）空间。
从上往下每层删除。
不能保证每层从左到右。
代码比较复杂，没有2个小时写不出来。
力扣Hard妥妥的。

pandami 发表于 2021-11-10 00:12
recursion的话，stack的空间也不能算吗？

是的stack也不能算

Amorw 发表于 2021-11-9 22:57
lc的一道medium题，我在面某中厂的时候也遇到了，因为做过写出来了。其实很简单，三个pointer，用上一层的p ...

这个想法面试的时候我也说了！！我也想到我连一下next不就是可以O1不用比的指针了，因为前面的轮次面过116这题，所以我还特意说其实我觉得可以改一下树，然后面试官立刻说了这个树不能修改。。。