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

1. 题目信息

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

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

示例 1:输入: [1,2,3]       1      / \     2   3输出: 6示例 2:输入: [-10,9,20,null,null,15,7]   -10   / \  9  20    /  \   15   7输出: 42

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 以当前节点为根的子树的最大值

  int curmax = root->val;if(left > 0)	curmax += left;if(right > 0)	curmax += right;

• 但是返回给上层使用的时候只能保留一边子树

  max(root->val, max(left+root->val, right+root->val))

  

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {
   	//C++public:    int maxPathSum(TreeNode* root) {
           int maxanswer = INT_MIN;        maxsum(root, maxanswer);        return maxanswer;    }    int maxsum(TreeNode* root, int &maxanswer)     {
       	if(root == NULL)    		return 0;    	int left = maxsum(root->left,maxanswer);    	int right = maxsum(root->right,maxanswer);    	int curmax = root->val;    	if(left > 0)        	curmax += left;        if(right > 0)        	curmax += right;        if(curmax > maxanswer)    		maxanswer = curmax;    	return max(root->val,max(left+root->val,right+root->val));    }};

• python3 解答

class Solution:# py3    def maxPathSum(self, root: TreeNode) -> int:        self.maxsum = float('-inf')        def dfs(root):            if not root:                return 0            l = dfs(root.left)            r = dfs(root.right)            v = root.val            curmax = v            if l>0:                curmax += l            if r>0:                curmax += r            self.maxsum = max(curmax, self.maxsum)            return max(v, max(v+l, v+r))        dfs(root)        return self.maxsum

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