Meta 树直径：边数、节点数与N叉两条最高分支

题意与假设

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

• 无权树，默认返回边数；节点数变体非空时边数+1，空树两种都返回0。
• N叉节点提供children，不含None。二叉树可用left/right构造children视图；每节点只有唯一父，非一般图。

解题路线

1. 后序height[node]是从node向下最长边数。每个child贡献height[child]+1，取最大的two branches，穿过node路径为one+two。
2. 全树直径最高转折点必是某node，两端各沿最多一条子分支；逐节点比较one+two即可覆盖所有端点，无需枚举两节点。
3. 局部best保存结果，不使用模块global；若面试禁止共享累加状态，递归返回(height,subtreeDiameter)将best作为子树返回值。示例显式后序实现同时避免递归深度。
4. N叉不必排序全部child高度，只线性维护第一/第二最大，总孩子数n−1，因此总体线性。

手动走一遍

单节点边数0/节点数1；根有三条高度2/4/3分支，穿根最长为4+3=7边，第三分支不能一并塞进简单路径。

Python 参考实现

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

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

def tree_diameter(root, count_nodes=False):
    """N-ary node.children; binary callers can expose children=[left,right] excluding None."""
    if root is None:return 0
    heights={};best=0;stack=[(root,False)]
    while stack:
        node,done=stack.pop()
        if not done:
            stack.append((node,True))
            stack.extend((child,False) for child in node.children)
        else:
            one=two=0
            for child in node.children:
                height=heights[id(child)]+1
                if height>one:one,two=height,one
                elif height>two:two=height
            heights[id(node)]=one
            best=max(best,one+two)
    return best+1 if count_nodes else best

复杂度

O(n)时间、示例O(n)高度表与显式栈空间。递归返回tuple可O(h)调用栈但深链仍有语言递归限制。

易错点与追问

容易失分的边界

• 把node高度按节点数定义却把直径按边数相加会差1。
• 只比较根穿越路径会漏掉最长路径完全处于某个子树。

继续深挖

• 返回实际路径需记录贡献最大的child和全局最佳转折点，分别恢复两支再拼接。
• 边有权时height加权，负权边需定义是否允许空路径及端点最少两个节点，不能照搬无权公式。