【二叉树】Leetcode 124. 二叉树中的最大路径和【困难】

二叉树中的最大路径和

• 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

解题思路

这个问题可以使用递归解决，对于每个节点：

• 1、以该节点为根的路径和（该路径和包括该节点，可能往左、往右、或者左右都有）。
• 2、以该节点的左子树为起点的最大路径和。
• 3、以该节点的右子树为起点的最大路径和。
• 4、取这三者的最大值作为以当前节点为根的最大路径和。

Java实现

public class MaxPathSum {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) {
            this.val = val;
        }
    }

    private int maxSum = Integer.MIN_VALUE;

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

    private int maxPathSumHelper(TreeNode node) {
        if (node == null) {
            return 0;
        }
//        10
//       /  \
//      2    10
//     / \     \
//    20  1     -25
//              / \
//             3   4

        // 计算以当前节点为根的路径和，可能包括左右子树
        int leftSum = Math.max(0, maxPathSumHelper(node.left));
        int rightSum = Math.max(0, maxPathSumHelper(node.right));

        // 更新全局最大路径和
        maxSum = Math.max(maxSum, leftSum + rightSum + node.val);

        // 返回以当前节点为根的路径和的最大值，注意不要包括左右子树
        return Math.max(leftSum, rightSum) + node.val;
    }

    // 示例测试
    public static void main(String[] args) {
        MaxPathSum solution = new MaxPathSum();

        // 构造二叉树
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(2);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(20);
        root.left.right = new TreeNode(1);
        root.right.right = new TreeNode(-25);
        root.right.right.left = new TreeNode(3);
        root.right.right.right = new TreeNode(4);

        int result = solution.maxPathSum(root);
        System.out.println(result); // 输出 42
    }
}

时间空间复杂度

• 时间复杂度：O(N)，其中 N 是二叉树中节点的数量，因为我们需要遍历每个节点。

• 空间复杂度：O(H)，其中 H 是二叉树的高度，因为递归调用栈的深度取决于二叉树的高度。