林荫Senior SDE电面跪

不用， 只用比较root的所有直系sibling 旁系的就不是第2小了

请问楼主面得哪个组啊？

所以lgn的解法是哪个啊？

请问是电话通知的吗

最坏情况是O(N)吧，https://leetcode.com/problems/se ... nary-tree/solution/

LC 原题啊 刘琦瑶

简单讲一下，如果所有叶节点的值都不相同，那么找到这个tournament tree(败者树)的最小值需要O(lgn)时间复杂度，因为每次比较可以排除一半的nodes

找到最小值后再借此寻找第二小的数字，同理又需要O(lgn)时间，所以最终的时间复杂度是O(2lgn) => O(lgn)

lc 原題最快應該是O(N)?

如果題目加上同一個節點的左右節點值不會相同才能O(logN)吧？

根节点就是全局最小值；所以我们要找第二最小值。

递归左右子树分别寻找第一个和根节点不一样的值，即为以当前节点为根的树的最小值。

每次比较左右子树的时候和根节点不一样的那边就可以停止比较了(因为已经找到结果了)，只需要进入另外一边(和根节点一样)继续寻找第一个和根节点不一样的值。

LC 没有distinct value这个条件吧，worst case整个树都都一个数，应该要O(N)