狗家热乎店面

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

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

这题真难，想了两天还是想不通。想问一下大家，如果把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

复制代码

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

sentolo 发表于 2021-04-21 14:01:23
dfs space complexity 是O(n), recursive本身调用栈，iteration也需要相应数据结构

不用递归，用iteration的话，也需要额外的空间存储nodes，比如stack。

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

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

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

这里如果是多叉树那么删除node应该怎么promote child node？

aug828 发表于 2021-4-21 17:12
应该就是在每个节点增加一个sum的值，每次增删节点的时候，更新所有父节点的sum。
不用父指针，也可以做到 ...

不是BST，那insert node有点不自然啊

jackalsin 发表于 2021-5-12 20:49
**** 本内容被作者隐藏 ****

clean code