题目描述

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

题目分析

树中任意一条路径，离 root 最近的结点可以视为路径的根结点。
对路径的根结点来说，最大路径 = 根结点值 + max(左结点出发最长路径，右结点出发最长路径，左结点出发最长路径 + 右结点出发最长路径)。
因此只需要递归计算从当前结点出发的最长路径，在过程中枚举路径的根结点，维护最大路径值。
每个结点只访问一次，时间复杂度 O(n)

Java

private int ans = -1001;

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

private int dfs(TreeNode root) {
    if (root == null) {
        return -1001;
    }
    int left = dfs(root.left);
    int right = dfs(root.right);
    int max = Math.max(left, right);

    ans = Math.max(ans, root.val);
    ans = Math.max(ans, max + root.val);
    ans = Math.max(ans, left + right + root.val);

    int length = Math.max(max, 0);
    return length + root.val;
}

Kotlin

private var ans = -1001

fun maxPathSum(root: TreeNode?): Int {
    dfs(root)
    return ans
}

// 从 root 出发最长路径
private fun dfs(root: TreeNode?): Int {
    if (root == null) {
        return -1001
    }
    val left = dfs(root.left)
    val right = dfs(root.right)
    val max = max(left, right)

    ans = ans.coerceAtLeast(root.`val`)
        .coerceAtLeast(max + root.`val`)
        .coerceAtLeast(left + right + root.`val`)

    return max.coerceAtLeast(0) + root.`val`
}