狗家热乎店面

刚刚面完，分享一下面经和心得

计算一个Tree的所有叶子sum，但是要space complexity O(1).

lz当时没想出来，硬着头皮先写了一个recursive求叶子sum的。

然后面试官提醒，可以从tree的数据结构入手。面试官听口音是个国人小哥，解释得我听不太清楚。

现在回想一下，一般思路是无法O(1) space complexity，所以要改变数据结构，查sum是O(1)，每次增删树节点的时候是O(log(n))

后面面试官提示了一下，自定义树的数据结构，加入parent和sum变量。勉勉强强写出来了，中间很多没有考虑清楚的细节被面试官一一指出。


下面是心得

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

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 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

直接morris traversal不行么? 在node里存东西难道不是额外空间么，我觉得这面试官有点恶心

这题真难，想了两天还是想不通。想问一下大家，如果把children从list改成doublelinkedlist，空间算是O(1)吗，像这样？

1. class Node:
   
2.     def __init__(self, val=None, children=None):
   
3.         self.val = val
   
4.         self.children = None
   
5.         self.next = None
   
6.         self.pre = None
   
7. 
   
8. 
   
9. 
   
10. def leavesOfSum(self, root: 'Node') -> 'Node':
    
11.     self.res = 0
    
12.     def helper(root):
    
13.         if not root: return
    
14.         node = root.children
    
15.         while node:
    
16.             if not node.children:
    
17.                 self.res += node.val
    
18.             helper(node)
    
19.             tmp = node
    
20.             if not node.pre and node.next:
    
21.                 node.next.pre = None
    
22.             elif not node.next and node.pre:
    
23.                 node.pre.next = None
    
24.                 node.pre = None
    
25.             elif node.next and node.pre:
    
26.                 node.pre.next = node.next
    
27.                 node.next.pre = node.pre
    
28.                
    
29.             node = node.next
    
30.             del tmp
    
31.                
    
32.     helper(root)
    
33.     return self.res

复制代码

如果能帮忙看一看，就非常感谢了！

是多叉树吗

好奇一下，只是space complexity O(1), 不是time. 不可以用dfs?

sum是O(1)，每次增删树节点的时候是O(log(n))，这个感觉是用segment tree的想法啊。加入/删除节点的时候需要go up to root node to do the update.

感谢分享

您好！
本帖隐藏的内容需要积分高于 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

lllxin37 发表于 2021-4-22 05:05
多谢回复. dfs的 space complexity是个灰色地带。有的公司接受栈的空间。

看样子，面试官就是想让你往 ...

是的，这个地方很细节。希望大家都能注意这一点吧

应该就是在每个节点增加一个sum的值，每次增删节点的时候，更新所有父节点的sum。
不用父指针，也可以做到。递归调用的时候小心一些就行了

匿名者 发表于 2021-4-22 04:03
是多叉树吗

yesyes字数字数

请问输入就是给了个root么