题解 | #二叉树中的最大路径和#
二叉树中的最大路径和
http://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a
这个题看了很多遍，感谢大佬们。
注意点：
1.深度遍历的是包括当前节点在内向下的最大节点和，因此可以避免重复计算。
2.更新的是最大路径和跟遍历的有点不一样，遍历向下的最大节点和只能选单边，路径是可以两边。
重点需要了解的是max(0,getMax(root->left))起到子节点为负数时忽略的功能。
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类
* @return int整型
*/
int res = INT32_MIN;
int maxPathSum(TreeNode* root) {
getMax(root);
return res;
}
int getMax(TreeNode* root){
if(root==NULL){
return 0;
}
if(root->left == NULL && root->right == NULL){
res = max({res,root->val});
return root->val;
}
int leftMax = 0;
int rightMax = 0;
leftMax = max(0,getMax(root->left));
rightMax = max(0,getMax(root->right));
res = max({res,root->val+leftMax+rightMax});
return root->val+max(leftMax,rightMax);
}
};
华为开奖670人在聊
投递创梦天地等公司8个岗位 >