Kotlin递归求树最长路径和返回值异常，预期结果为20

你的代码存在两个核心逻辑错误，导致结果异常：

• 递归逻辑混淆了两种路径和的计算：当前函数错误地将「经过当前节点的跨子树路径和」与「从当前节点向下延伸的单路径和」混为一谈，递归返回值完全不符合需求。
• 叶子节点处理不当：叶子节点的左右子节点为null时，你用Int.MIN_VALUE替代，导致计算时出现负数叠加甚至整数溢出，最终得到错误的负数结果。

你构建的树中，预期的最大路径和是5 + 11 + 4 = 20（根节点→左子节点11→右子节点4），以下是修正后的实现：

修正后的代码 #

class TreeNode<T>(var key: T) {
    var left: TreeNode<T>? = null
    var right: TreeNode<T>? = null
}

fun maxPathSum(root: TreeNode<Int>): Int {
    var maxSum = Int.MIN_VALUE

    // 递归计算从当前节点向下延伸的最大单路径和，同时更新全局最大路径和
    fun maxPathFromNode(node: TreeNode<Int>): Int {
        val leftSum = node.left?.let { maxPathFromNode(it) } ?: 0
        val rightSum = node.right?.let { maxPathFromNode(it) } ?: 0

        // 计算经过当前节点的跨子树路径和，更新全局最大值
        val currentCrossSum = node.key + leftSum + rightSum
        if (currentCrossSum > maxSum) {
            maxSum = currentCrossSum
        }

        // 返回当前节点作为路径端点的最大单路径和（若左右子树路径和为负则放弃）
        return node.key + maxOf(leftSum, rightSum, 0)
    }

    maxPathFromNode(root)
    return maxSum
}

fun buildTree3(): TreeNode<Int> {
    val one = TreeNode(1)
    val two = TreeNode(2)
    val three = TreeNode(3)
    val four = TreeNode(4)
    val five = TreeNode(5)
    val eleven = TreeNode(11)

    five.left = eleven
    five.right = three
    eleven.right = four
    eleven.left = two
    three.right = one

    return five
}

// 测试调用
fun main() {
    println("-------Max Root to Leaf Path Sum-------")
    println(maxPathSum(buildTree3())) // 输出20
}

代码说明 #

1. 拆分递归职责：用内部函数maxPathFromNode计算从当前节点向下延伸的最大单路径和，同时在递归过程中更新全局变量maxSum（记录所有可能的跨子树路径的最大值）。
2. 合理处理空节点：空节点的路径和用0代替，若子树路径和为负数则直接放弃该子树，避免拉低整体路径和。
3. 全局最大值记录：每次递归时计算「当前节点+左单路径+右单路径」的和，这是经过当前节点的最大路径和，用于更新全局最大值。

运行修正后的代码，会输出预期的20。

内容的提问来源于stack exchange，提问作者OEThe11