前言:
每道题附带动态示意图, 提供 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
结果:
来源: https://www.cnblogs.com/nedulee/p/12019493.html