LC543　二叉树的直径¶

简单通过率 64.4%python3核心代码模式二叉树样例通过牛客 AC树深度优先搜索二叉树树形 DP

一句话

每个节点算一次「左右两棵子树的高度之和」，取最大值。

解题思路¶

这题考什么¶

直径是任意两点间最长路径的边数。它和 LC124 的最大路径和同构：任何一条路径都有唯一的最高点，以最高点为界拆成两条向下的链。于是把「枚举路径」换成「枚举最高点」：

以 node 为最高点的最长路径边数 = 左子树高度 + 右子树高度

这里的「高度」按节点数算：空子树高度 0，叶子高度 1。两个节点数之和为什么恰好就是边数？因为左边那条链有 h_left 个节点，从 node 走到它的末端要跨 h_left 条边（node 到左孩子算第一条），右边同理，合起来正是 h_left + h_right 条边。

高度本身满足 h(node) = max(h(左), h(右)) + 1，是一次后序遍历就能算完的量：先把两个孩子结算好，再结算自己。这是树形动态规划（树形 DP）的最小样例，树的直径的两种做法见树的基础与遍历的「树的直径」一节。

示例 1 的 [1,2,3,4,5]：

叶子 4、5、3 的高度都是 1
node = 2：候选 1 + 1 = 2；h(2) = 2
node = 1：候选 2 + 1 = 3

返回 3，对应路径 4 -> 2 -> 1 -> 3，与样例一致。

数据规模与复杂度¶

节点数在 [1, 10^4]，节点值在 [-100, 100]（值与答案无关，只有形状有关）。每个节点被展开一次、结算一次，时间 O(n)；栈与高度表都是 O(n)（栈深不超过树高，链状树就是 n）。

坑在哪¶

必须迭代。n 到 1e4，最坏是一条链，递归深度 1e4，远超 CPython 默认的 1000 层上限，递归版 RecursionError；递归改迭代见 DFS 深度优先搜索的 60.4 节。这里用「进出两次」的后序遍历：第一次弹出只把自己和两个孩子重新压栈，第二次弹出时孩子的高度都已经算好了。
答案按边数、高度按节点数，两个口径不能混。单节点树的直径是 0 而不是 1；直接返回最大高度之类的写法会整体差一。
最长路径不一定经过根。示例里过根只是巧合，所以必须对每个节点都算一次候选值；只在根上算一次会漏掉挂在深处的长路径。
高度表用节点的 id 当键，空孩子查不到时默认 0 —— 这正好就是「空子树高度为 0」，不需要额外的判空分支。
答案初值取 0：题面保证至少一个节点，而单节点树没有任何边，直径就是 0，不存在比它更小的合法答案。

参考实现¶

solutions/leetcode/LC543/sol.py
from typing import List, Optional


class Solution:
    def diameterOfBinaryTree(self, root: "Optional[TreeNode]") -> int:
        # 直径按边数算，单节点树是 0，所以 0 就是答案的下界
        best = 0
        # id(节点) -> 该节点的高度（按节点数算：叶子为 1，空子树为 0）
        height = {}
        # 栈元素是 (节点, 是否已展开)。False 只负责安排孩子，
        # True 表示两个孩子都结算完了、轮到自己 —— 后序遍历的迭代写法
        stack = [(root, False)]
        while stack:
            node, expanded = stack.pop()
            # 空子树高度为 0，不必进表，弹出即跳过
            if node is None:
                continue
            if not expanded:
                # 自己以 True 压在两个孩子下面，保证孩子先结算
                stack.append((node, True))
                stack.append((node.left, False))
                stack.append((node.right, False))
                continue
            # 查不到就是空孩子，默认 0 正好对应「空子树高度为 0」
            left = height.get(id(node.left), 0)
            right = height.get(id(node.right), 0)
            # 以 node 为最高点的路径边数 = 两侧高度之和；每个节点都要算一次候选
            best = max(best, left + right)
            # 自己的高度 = 较高的一侧再加上自己这一层
            height[id(node)] = max(left, right) + 1
        return best

LC543 二叉树的直径¶