二叉树的直径

问题拆解

直径是任意两节点间最长路径的边数，这条路径可能穿过根，也可能不穿过。如果对每个节点都单独去搜一遍最长路径，复杂度会很高，而且大量深度会被重复计算。

关键洞察是换一个统计口径：任何一条路径,都有一个「最高点」——路径上离根最近的那个节点。以某个节点为最高点的最长路径,恰好是它左子树深度加右子树深度。于是直径就是所有节点这个值的最大者。

与其枚举路径，不如枚举路径的转折点：每个节点贡献一个「左深 + 右深」，取全局最大即可。

求深度时顺带更新

我们本来就要为每个节点算深度，那就在同一趟递归里，把「左深 + 右深」拿去刷新一个全局最大值：

def diameterOfBinaryTree(root):
    best = 0

    def depth(node):
        nonlocal best
        if not node:
            return 0
        left = depth(node.left)
        right = depth(node.right)
        best = max(best, left + right)
        return 1 + max(left, right)

    depth(root)
    return best

depth 的返回值仍然是老老实实的子树深度，供上层使用；而 best 只在递归内部被悄悄更新。返回值和副作用各司其职，是这类题的常见分工。注意直径按边数计，所以是 left + right 而不用再加一。

复杂度

指标	复杂度	原因
时间	O(n)	深度只在一趟后序遍历中算完
空间	O(h)	递归栈深度等于树高

可以迁移的模式

• 求「路径最值」时，把路径按其最高点归类，往往能把二维搜索压成一维统计；
• 递归函数可以「返回一个量给上层，同时用副作用维护另一个全局量」；
• 遇到「最长路径」「最大和路径」这类树形问题，先想想每个节点作为转折点能贡献什么。

一次遍历同时算两件事，是把暴力枚举优化掉的常见手法。