NC6 二叉树的最大路径和

vlambda
2021-07-21

NC6 二叉树的最大路径和

情景提要

牛客题解系列，按照题号顺序开始。

NC6 二叉树的最大路径和

题目描述

NC6 二叉树的最大路径和

输入输出示例

输入:

{-2,1}

输出:

题目分析

思路

最大路径中，是不一定经过根节点的。但我们可以递归，统计每个子树的最大路径和，取最大的即可。

首先思考遍历方式。使用左右中，即后序遍历的方式，遍历每个结点。

对于每个结点，统计以当前结点为根节点且经过当前结点时的最大和。

具体可以仔细品代码，一切尽在不言中。

一个字，妙。

代码实现

方法1

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */class Solution {public: /** *  * @param root TreeNode类  * @return int整型 */ int maxsum; int maxPathSum(TreeNode* root) { // write code here maxsum = root->val; travel(root); return maxsum; } int travel(TreeNode* node){ if(node == nullptr) return 0; //左右中 后序遍历 int leftval = travel(node->left); int rightval = travel(node->right); //更新当前最大的值 int curmax = max({0,leftval})+node->val+max(0,rightval); maxsum = max(maxsum,curmax); return node->val + max({0,leftval,rightval}); //妙啊 }};