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

r0_0e 发表于 2021-11-9 23:12
你说的这个是 摇姚遛。

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

感觉这个方法是最有可能的吧，我理解的是第1种需求，因为我写了一半Morris从4走到3的时候面试官说了一句不符合从上到下。但是看了你写的这个链表，moveRightChildToLeftChildBottom的话，那虽然在原二叉树上不是从上到下但是也满足了一直从上到下？？我当时的思路也是怎么把右边的节点移到左下边，但是moveRightChildToLeftChildBottom这个函数用O1根本想不出来 ：p

补充内容 (2021-11-11 01:13 +8:00):
而且我其实当时仔细问过从上到下是不是就是要按层删，但是面试官就是强调只需要从上到下，感觉就是可能说明白了我就明白了移动的这个意思？
不过到现在我也不知道怎么move，感觉move是不是还是要占额外空间。。。

paopaojeffrey 发表于 2021-11-9 22:51
这么卷，要我就直接换一家

这个是第四轮了，前三轮虽然也经常H题但是都还比较经典，面试官也挺好的其实一直提示，第二题也给了到比较简单的（虽然最后的最后还是留下了一个小bug TT）

xxnooryesxx 发表于 2021-11-10 07:45
感觉这个方法是最有可能的吧，我理解的是第1种需求，因为我写了一半Morris从4走到3的时候面试官说了一句 ...

如果是套用Morris来做前序遍历，应该也是可以达到 父节点先于子节点删除 的。

比如这个二叉树
      1
  2      3
4  5  6  7

按照题目的要求，访问的顺序就是
1 2 4 5 3 6 7
能看出来，也是满足父节点先于子节点删除的。

但是不能直接，因为Morris的套路里，在处理节点1的时候，他是先往左孩子的最右去找，也就是找到节点5，把节点5的右孩子指到节点1去，然后对节点1做访问处理。后面访问到节点5的时候，需要利用节点5的右孩子回到节点1，从而能够继续处理节点2。

但是我们这个题的要求是删除节点，也就是说，当我们处理完节点1后，就是把节点1删除了。那么我们后边访问到节点5，从节点5的右孩子回不到节点1了（因为节点1之前被删除了），那么节点2那边就无法处理了。

所以我前面说的那个，就是在处理节点1的时候，把节点2给挂到节点4下面去了。这样就没有回到节点1然后再处理节点2的问题了，因为都已经挂到下面了。

但是你又提到了面试官说，原来的树不允许改……
那我觉得真的没解了……
怀疑这个面试官脑子清楚不清楚。

因为遍历一个二叉树，无论前序中序后序，想要实现空间复杂度O1的话，目前我知道的就Morris，然而这个是需要改树的，只不过他在访问之后又改了回来（就是开始把5的右孩子指到1，处理完之后又把5的右孩子设置成null，也就是变回原来的值）。处理的过程当中，还是需要改的。

如果处理过程中不允许改树，那Morris也不行，还有其他的空间复杂度O1的算法么？

具体到这个题，因为要求的是删除树，意味着操作完一个节点，就是把这个节点删除了，那就没有改回来的可能了，人都没了，改谁去？

最后说MoveRightToLeftBottom，你都看了Morris了，那这个也应该是手到擒来呀。
时间上的O1是不可能的，空间O1妥妥的。

1. //pseudo code
   
2. public void MoveRightToLeftBottom(TreeNode node) {
   
3.   if(node == null) return; // no need to process
   
4.   if(node.right == null) return; // no right child
   
5.   
   
6.   TreeNode right = node.right; // store right child of given node
   
7.   TreeNode cur = node;
   
8.   while(cur.left != null) {
   
9.     cur = cur.left;
   
10.   } // find the most left leaf
    
11.   cur.left == right; // set most left leaf right child to given node's right child
    
12.   node.right = null; // remove given node's right child
    
13. }

复制代码

r0_0e 发表于 2021-11-10 13:52
如果是套用Morris来做前序遍历，应该也是可以达到 父节点先于子节点删除 的。

比如这个二叉树

我研究了一下你的方法，感觉十有八九就是这样了！
我说的不允许改树是因为本来我想在树里加个next节点，就像上面说的那题一样，加完了就可以只知道每层第一个点之后把整层删掉。但是现在想想也不对，因为连接next好像还是需要Oh的空间去连，好像O1连不了。。

这个确实应该满足了O1空间和一直从上向下删。现在看感觉就是Morris的变种。刚才也复盘了下我当时写的Morris也不对所以面试官没看出来也正常。希望这半轮凉了不要抹去我前3轮的努力。。。。

其实一般层序遍历的BFS删除，如果你把删除的space和queue用到的space加一起总space是不变的。当然这是玩文字游戏了，层序遍历可以保证从上到下，从左到右

r0_0e 发表于 2021-11-10 13:52
如果是套用Morris来做前序遍历，应该也是可以达到 父节点先于子节点删除 的。

比如这个二叉树

破案了！我今天看我的小本本，找到了这道题应该就是利口妖妖似，普通解法On，第三种解法是O1空间。只不过面试官没问原题，而是像我最开始说的那种问法。所以最后我碎碎念链表的时候他也说了就是链表。诶亏了我还做过但是估计当时也没看O1的解法，面试的时候也没琢磨过来 =^=

xxnooryesxx 发表于 2021-11-11 16:44
破案了！我今天看我的小本本，找到了这道题应该就是利口妖妖似，普通解法On，第三种解法是O1空间。只不过 ...

我跑去看了一下，经典的树转链，保证先序遍历顺序。

之前跟同事聊天的时候聊过，哈哈哈哈。

看来跟面试官澄清需求很重要，能厘清很多东西。

1. public void flatten(TreeNode root) {
   
2.   TreeNode cur = root;
   
3.   while(cur != null) {
   
4.     if(cur.left == null) {
   
5.       cur = cur.right;
   
6.       continue;
   
7.     }
   
8.     TreeNode predecessor = cur.left;
   
9.     while(predecessor.right != null) {
   
10.       predecessor = predecessor.right;
    
11.     }
    
12.     predecessor.right = cur.right;
    
13.     cur.right = cur.left;
    
14.     cur.left = null;
    
15.   }
    

复制代码

r0_0e 发表于 2021-11-11 20:55
我跑去看了一下，经典的树转链，保证先序遍历顺序。

之前跟同事聊天的时候聊过，哈哈哈哈。

确实想到过类似的思路
1
23
4567
当时就是用这个树举例子，因为知道个Morris的大概，所以想了个不成熟的类似走1245367的思路但是一直是想着如何存prev结点而不是把右子树移到左下，然后面试官说你这不是还是45走完了走到上一层的3不符合一直往下走。然后我就再也没想过这条路了。。。