王位继承

umialpha 发表于 2019-3-27 19:50
写了一个double linked list的方案， listnode里多一个指针指向最后一个孩子节点。但是这样做birth不再是O( ...

有个问题，42， 43行，为什么要用while循环？会不会导致本来是王的最后一个儿子变成最后一个皇子的最后一个儿子。

llss22 发表于 2019-4-9 04:54
写了一个python的code，欢迎大家讨论指正
用linkedlist和map
birth的话，找到parent的last child O(1),  ...

如果death的节点刚好是 其父节点的 last child呢？ 好像你没做处理啊？

summernight 发表于 2019-4-10 02:10
我觉得你说的是对的，光维护LastChild不够，问题在于最小儿子A的儿子B出生后，如果父亲C又有了一个新儿子 ...

保存每个节点的儿子的两个边界left和right应该就可以解决这个问题了

补充内容 (2019-5-2 15:11):
好像不对，还得再想想

补充内容 (2019-5-2 15:11):
好像不对，还得再想想