Tiktok 面经

前面聊项目花的时间有点久。

做了一道flatten binary tree

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

有问题，只保存前一节点，实现不了中序遍历吧。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

有一个很巧的方法是可以做到O(1) 的space并且不是recursive
直接贴蠡口的答案了

1. class Solution {
   
2.     public void flatten(TreeNode root) {
   
3.         // Handle the null scenario
   
4.         if (root == null) {
   
5.             return;
   
6.         }
   
7.         TreeNode node = root;
   
8.         while (node != null) {
   
9.             // If the node has a left child
   
10.             if (node.left != null) {
    
11.                 // Find the rightmost node
    
12.                 TreeNode rightmost = node.left;
    
13.                 while (rightmost.right != null) {
    
14.                     rightmost = rightmost.right;
    
15.                 }
    
16.                 // rewire the connections
    
17.                 rightmost.right = node.right;
    
18.                 node.right = node.left;
    
19.                 node.left = null;
    
20.             }
    
21.             // move on to the right side of the tree
    
22.             node = node.right;
    
23.         }
    
24.     }
    
25. }

复制代码

postorder traversal

麻倉枼 发表于 2020-12-18 02:57
postorder traversal

flatten binary tree经典题目，变种很多，要根据具体情况来做，我遇到的是in-order哈

如果recursive写就应该不需要额外内存了吧 （recursion call stack 不算额外的前提下）

匿名的 发表于 2020-12-18 04:01
如果recursive写就应该不需要额外内存了吧 （recursion call stack 不算额外的前提下）

recursive跟手动操作辅助stack应该是一样的空间消耗吧？

lz收到结果了吗？已加米

yiliaobailiao 发表于 2020-12-18 04:33
recursive跟手动操作辅助stack应该是一样的空间消耗吧？

算recursion call stack就是一样~

匿名者 发表于 2020-12-17 14:05
flatten binary tree经典题目，变种很多，要根据具体情况来做，我遇到的是in-order哈

没看到要in-place不好意思。如果面试官stack memory也算进去的话，全部recursion都不用考虑了