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

Binary Tree Maximum Path Sum 二叉树中的最大路径和

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

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

输入:

[1,2,3]       1      / \     2   3

输出:

6

方法一：递归

二叉树abc，a是根结点（递归中的root），bc是左右子结点（代表其递归后的最优解）。

a   / \  b   c

1. b + a + c。
2. b + a + a的父结点。
3. a + c + a的父结点。

其中情况 1 ，表示如果不联络父结点的情况，或本身是根结点的情况。这种情况是没法递归的，但是结果有可能是全局最大路径和。

另外结点有可能是负值，最大和肯定就要想办法舍弃负值（max(0, x)）。

代码中使用 val 来记录全局最大路径和。

所要做的就是递归，递归时记录好全局最大和，返回联络最大和。

int maxPathSum(TreeNode* root, int &val){
   	if (root == nullptr) return 0;	int left = maxPathSum(root->left, val);	int right = maxPathSum(root->right, val);	int lmr = root->val + max(0, left) + max(0, right);	int ret = root->val + max(0, max(left, right));	val = max(val, max(lmr, ret));	return ret;}int maxPathSum(TreeNode* root) {
   	int val = INT_MIN;	maxPathSum(root, val);	return val;}

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