二叉树最大路径和问题解析 | 算法详解与代码实现

在二叉树中，最大路径和问题是一个经典的算法问题。给定一个二叉树，你需要找到一条路径，使得路径上节点值的和最大。这条路径可以从任意节点开始，到任意节点结束，但必须遵循树的父子关系。

问题分析

1. 路径定义：路径可以是任意节点到任意节点的路径，只要它们之间存在父子关系。
2. 最大路径和：我们需要找到所有可能的路径中，节点值之和最大的那个路径。

解决思路

我们可以使用递归的方法来解决这个问题。对于每个节点，我们需要计算以下两种情况：

1. 以当前节点为根的子树中的最大路径和：这个路径可以包含当前节点，也可以不包含。
2. 以当前节点为起点的最大路径和：这个路径必须包含当前节点，并且只能向下延伸。

算法步骤

1. 递归函数：定义一个递归函数 maxGain(node)，它返回以 node 为起点的最大路径和。
2. 计算左右子树的最大路径和：对于当前节点，递归计算左子树和右子树的最大路径和。
3. 更新全局最大路径和：在递归过程中，更新全局的最大路径和。
4. 返回当前节点的最大路径和：返回以当前节点为起点的最大路径和。

代码实现

function maxPathSum(root) {
    let maxSum = -Infinity;

    function maxGain(node) {
        if (node === null) return 0;

        // 递归计算左右子树的最大路径和
        let leftGain = Math.max(maxGain(node.left), 0);
        let rightGain = Math.max(maxGain(node.right), 0);

        // 计算当前节点的最大路径和
        let priceNewpath = node.val + leftGain + rightGain;

        // 更新全局最大路径和
        maxSum = Math.max(maxSum, priceNewpath);

        // 返回以当前节点为起点的最大路径和
        return node.val + Math.max(leftGain, rightGain);
    }

    maxGain(root);
    return maxSum;
}

复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树中的节点数。每个节点只会被访问一次。
• 空间复杂度：O(H)，其中 H 是二叉树的高度。递归调用栈的深度取决于树的高度。

示例

假设有以下二叉树：

      1
     / \
    2   3

调用 maxPathSum(root) 将返回 6，因为路径 2 -> 1 -> 3 的和最大。

总结

通过递归和动态规划的思想，我们可以高效地解决二叉树的最大路径和问题。这个算法不仅适用于二叉树，还可以扩展到更复杂的树结构。