题目描述

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

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

示例 1:

输入: [1,2,3]

​ 1

​ / \

​ 2 3

输出: 6

示例 2:

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

-10

/ \

9 20

​ / \

15 7

输出: 42

解题思路

递归，每个时刻判断左子树和右子树的值，如果子树的值大于0，则加上子树的值，同时利用全部变量maxpath记录递归过程中的最大值。

先定义一个全局变量来存储计算过程中的最大路径。

写一个函数nowToother(TreeNode* node)

函数有两个作用：

1. 返回从node出发到另一节点的最大路径

2. 更新最大路径（因为函数用用了全局变量maxpath）

（1） node为起点，终点在node的右子树（lmaxpath<0, rmaxpath>0）

（2）node为起点，终点在node的左子树（lmaxpath>0, rmaxpath<0）

（3）起点和终点分别在左右子树，但经过node （lmaxpath<0, rmaxpath>0）

（4）Node即为起点又是终点（lmaxpath<0, rmaxpath<0）

函数原理：

源代码

class Solution { public: ​ int maxpath=INT_MIN;//全局变量，用于存储节点路径的最大值 ​ int nowToother(TreeNode* node){//计算从node节点出发到其他节点的最大值 ​ if(node==NULL)return 0; ​ int temp=node->val;//存储node（出发点的值） ​ int lmaxpath=nowToother(node->left);//计算出发点node左孩子的从左孩子出发到其他节点的最大值 ​ int rmaxpath=nowToother(node->right);//右 ​ if(lmaxpath>0)temp+=lmaxpath;//如果从左孩子出发到其他节点的最大值大于零则把左孩子和node连起来 ​ if(rmaxpath>0)temp+=rmaxpath;//同理也把右边连起来 ​ //注意如果，左右都被连了起来，那么node就不是出发点了 ​ if(maxpath<temp)maxpath=temp;//更新当前最大路径 ​ //用于计算从node出发到另一节点的最大值 ​ return max(node->val,max(node->val+lmaxpath,node->val+rmaxpath)); ​ } ​ int maxPathSum(TreeNode* root) { ​ if(root==NULL)return 0; ​ nowToother(root); ​ return maxpath; ​ } };