三叉树众数与Broken Tree：频数正确性先于排序优化

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 值可排序可hash，正常结构每个节点最多left/middle/right三孩子。返回所有并列众数升序。
• 代码即使值顺序损坏仍正确统计；环或共享节点视为不是树并拒绝。若要图上唯一节点频数，合同不同。

解题路线

1. 稳健基线用DFS遍历每个节点计频，再取最大频数的所有值；不依赖排序性质，因此能覆盖值放错分支的broken tree。
2. 正常三叉搜索树可讨论中序left→node→middle→right是否在全局搜索树约束下形成非降序，从而连续值计数。仅局部孩子比较不保证整棵全局有序，不能据此删hash。
3. seen身份集防环和共享子节点重复计数。区分空树、全并列、重复值链、结构坏与排序坏；不存在默默把环忽略再声称树已修复的行为。

手动走一遍

值[2,1,2,3,3]众数为[2,3]；把3误放left仍能统计。root.left=root应拒绝，不能递归到栈溢出。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import Counter
class Node:
    def __init__(self,value,left=None,middle=None,right=None):
        self.value=value;self.left=left;self.middle=middle;self.right=right

def modes(root):
    if root is None:return []
    counts=Counter();seen=set();stack=[root]
    while stack:
        node=stack.pop()
        if id(node) in seen:raise ValueError("cycle or shared node; not a tree")
        seen.add(id(node));counts[node.value]+=1
        stack.extend(x for x in (node.left,node.middle,node.right) if x is not None)
    maximum=max(counts.values())
    return sorted(value for value,count in counts.items() if count==maximum)

复杂度

n节点O(n)遍历、O(n)seen+O(d)频数，输出排序O(klogk)，d不同值k众数数。

易错点与追问

容易失分的边界

• 假设middle只一个重复节点会漏长链。
• 返回第一个最大值会漏并列众数。

继续深挖

• 若只允许O(h)辅助空间，需要怎样验证全局有序不变量？
• broken只指缺失指针时为什么不等于循环引用？