本文共 1282 字，大约阅读时间需要 4 分钟。

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

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

示例 1：

输入：[1,2,3]

1  / \ 2   3

输出：6

示例 2：

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

-10

/

9 20

/

15 7

输出：42

解题思路：

首先，考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。

具体而言，该函数的计算如下。

• 空节点的最大贡献值等于 00。
• 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。

package com.lcz.leetcode;// 二叉树中的最大路径和public class Leetcode124 {
   	// 二叉树结点	class TreeNode{
   		int val;		TreeNode left;		TreeNode right;		TreeNode(){
   					}		TreeNode(int val){
   			this.val = val;		}		TreeNode(int val,TreeNode left,TreeNode right){
   			this.val = val;			this.left = left;			this.right = right;		}	}	class Solution {
   		int res = Integer.MIN_VALUE;	    public int maxPathSum(TreeNode root) {
   	    	maxGain(root);	    	return res;	    }	    public int maxGain(TreeNode node) {
   	    	// 递归截止条件	    	if(node==null) {
   	    		return 0;	    	}	    		    	// 递归计算左节点的最大贡献值	    	int leftGain = Math.max(maxGain(node.left), 0);	    	int rightGain = Math.max(maxGain(node.right), 0);	    		    	// 当前节点最大路径和	    	int tempPath = node.val + leftGain + rightGain;	    	res = Math.max(res, tempPath);	    		    	// 返回当前节点的最大贡献值	    	return node.val + Math.max(leftGain,rightGain);	    }	}}

转载地址：https://codingchaozhang.blog.csdn.net/article/details/111568751 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！