vvrf / DSA.log

问题拆解

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

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

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

求深度时顺带更新

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

private int best = 0;

public int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return best;
}

private int depth(TreeNode node) {
    if (node == null) return 0;
    int left = depth(node.left);
    int right = depth(node.right);
    best = Math.max(best, left + right);
    return 1 + Math.max(left, right);
}

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

func diameterOfBinaryTree(root *TreeNode) int {
    best := 0
    var depth func(node *TreeNode) int
    depth = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := depth(node.Left)
        right := depth(node.Right)
        best = max(best, left+right)
        return 1 + max(left, right)
    }
    depth(root)
    return best
}

pub fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    fn depth(node: &Option<Rc<RefCell<TreeNode>>>, best: &mut i32) -> i32 {
        match node {
            None => 0,
            Some(n) => {
                let n = n.borrow();
                let left = depth(&n.left, best);
                let right = depth(&n.right, best);
                *best = (*best).max(left + right);
                1 + left.max(right)
            }
        }
    }
    let mut best = 0;
    depth(&root, &mut best);
    best
}

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

复杂度

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

可以迁移的模式

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

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