day6 二叉树最大路径和_vlambda技术博客

vlambda
2021-04-17

day6 二叉树最大路径和

https://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a

题解：

这道题比较难，首先一定要理解题意。题目的意思是在二叉树中找一条路径，其结点和是所有路径中最大的，并返回这个和的值。

接下来就需要仔细分析一下这道题。最大路径和有三种可能：

1.只有一个结点

2.以一个结点为起点，向其左子树或向右子树延伸

3.从左子树上某个结点为起点，延伸到父节点，然后延伸到右子树

那么可以定义一个函数GetMax，它的作用是获取以当前结点为起点的最大路径和，假设当前结点为node，那么以该结点为起点的路径最大和应为node->val、GetMax（node->left）+ node->val、GetMax（node->right）+ node->val、GetMax（node->left）+ GetMax（node->right）+ node->val中的最大值。如此只需要遍历整棵树，然后找出那个最大值即可。下面给出代码，请你务必理解GetMax的返回值。

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
class Solution {public: /** *  * @param root TreeNode类  * @return int整型 */    int res = INT_MIN; //用一个全局变量记录最大的路径和 int GetMax(TreeNode* node){ if(node == NULL) return 0; int leftMax = GetMax(node->left); int rightMax = GetMax(node->right); int temp = max(node->val,max(max(leftMax,rightMax)+node->val,                      leftMax+rightMax+node->val));         //temp是以当前结点为起点的最大路径和 res = max(res,temp); return 0 > max(leftMax,rightMax)? node->val: max(leftMax,rightMax) + node->val;        //不要忘记GetMax函数真正的作用    } int maxPathSum(TreeNode* root) { // write code here GetMax(root); return res; }};