图解leetcode —— 124. 二叉树中的最大路径和

前言：

每道题附带动态示意图，提供java、python两种语言答案，力求提供leetcode最优解。

描述：

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1：

输入: [1,2,3]

1
/ \
2 3

输出: 6

示例 2：

输入: [-10,9,20,null,null,15,7]

-10
/ \
9 20
/ \
15 7

输出: 42

思路：

java:

class Solution {

    /**

     * 最大路径和

     */

    private int sum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {

        maxGain(root);

        return sum;

    }

    public int maxGain(TreeNode node) {

        if (node == null) {

            return 0;

        }

        // 小于0的权值舍弃，代表不走该节点

        int leftGain = Math.max(maxGain(node.left), 0);

        int rightGain = Math.max(maxGain(node.right), 0);

        int pathGain = leftGain + rightGain + node.val;

        sum = Math.max(sum, pathGain);

        // 返回最大路径，路径被定义为一条从树中任意节点出发，达到任意节点的序列。

        return node.val + Math.max(leftGain, rightGain);

    }

}

结果：

python:

import sys

class Solution:

    def maxPathSum(self, root: TreeNode) -> int:

        def max_gain(node: TreeNode) -> int:

            nonlocal max_sum

            if not node:

                return 0

            left_gain = max(max_gain(node.left), 0)

            right_gain = max(max_gain(node.right), 0)

            path_gain = left_gain + right_gain + node.val

            max_sum = max(max_sum, path_gain)

            return node.val + max(left_gain, right_gain)

        # 负无穷

        max_sum = float('-inf')

        max_gain(root)

        return max_sum

巴特西

图解leetcode —— 124. 二叉树中的最大路径和

前言：

描述：

示例 1：

示例 2：

思路：

java:

结果：

python:

结果：

最新文章

热门文章