树的直径与路径长度

这两题都需要在后序 DFS 中进行"全局更新"，用一个变量记录答案，同时向上返回"单路径"最大值。

二叉树的直径（LeetCode 543）

直径 = 通过某节点的左深度 + 右深度（不一定经过根）。

private int ans = 0;

public int diameterOfBinaryTree(TreeNode root) {
    dfs(root);
    return ans;
}

// 返回从 node 出发的最长单侧路径长度
private int dfs(TreeNode node) {
    if (node == null) return 0;
    int left  = dfs(node.left);
    int right = dfs(node.right);
    ans = Math.max(ans, left + right);  // 更新全局最大直径
    return Math.max(left, right) + 1;  // 向父节点返回单侧最大深度
}

关键：ans 取 left + right（不加1），return 时取 max + 1。

二叉树中的最大路径和（LeetCode 124）

路径不要求经过根，节点可为负值。

private int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    gain(root);
    return maxSum;
}

// 返回从 node 出发（向下延伸）的最大路径和（负则返回0，即不选择该方向）
private int gain(TreeNode node) {
    if (node == null) return 0;
    int leftGain  = Math.max(gain(node.left),  0);  // 负数就不选
    int rightGain = Math.max(gain(node.right), 0);
    // 当前节点作为路径最高点时的路径和
    maxSum = Math.max(maxSum, node.val + leftGain + rightGain);
    // 向上只能返回单侧
    return node.val + Math.max(leftGain, rightGain);
}

与直径对比：

树中最长的连续序列（LeetCode 298）

父→子方向，相邻节点值要连续递增（val + 1 == child.val）。

private int maxLen = 0;

public int longestConsecutive(TreeNode root) {
    dfs(root, null, 0);
    return maxLen;
}

private void dfs(TreeNode node, TreeNode parent, int len) {
    if (node == null) return;
    int curr = (parent != null && node.val == parent.val + 1) ? len + 1 : 1;
    maxLen = Math.max(maxLen, curr);
    dfs(node.left,  node, curr);
    dfs(node.right, node, curr);
}

总结

后序 DFS 模板（全局最大更新）

int ans = 初始值;

int dfs(node) {
    if null → return 基础值（0 或 MIN）
    left  = dfs(node.left)
    right = dfs(node.right)
    ans = max(ans, 利用 left/right/node.val 的组合)   // 全局更新
    return 向上传递的单侧值                              // 供父节点使用
}

适用题型：直径、最大路径和、最大子序列长度等。