二叉树的题目虽然标着hard类型,但解起来有点爽,这道题目琢磨透了觉得非常的棒,可以说这种类型题目是一种套路。可以结合文章段错误segment fault分析一起使用更佳。或许屏幕前的朋友会有疑问,这篇讲函数调用栈的文章和leetcode124有啥关系?其实树里面很多递归的逻辑就是函数调用,直到调用到终止条件,然后层层向上返回的过程。
题目:
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example 1:
Input: [1,2,3]
1
/ \
2 3
Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
Output: 42
解法:
/**
* 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 {
int maxPathSum(TreeNode *root, int &re) {
if(NULL == root)
{
return 0;
}
int l = maxPathSum(root->left,re);
int r = maxPathSum(root->right,re);
l = (l < 0) ? 0 : l;
r = (r < 0) ? 0 : r;
if(l + r + root->val > re)
re = l + r + root->val;
return root->val += max(l, r);
}
public:
int maxPathSum(TreeNode* root) {
int max = INT_MIN;
maxPathSum(root, max);
return max;
}
};
配合如下输出,在leetcode中运行,结合输出结果理解更佳
/**
* 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 {
int maxPathSum(TreeNode *root, int &re) {
if(NULL == root)
{
printf("call func maxPathSum,root NULL,re = %d.\n",re);
return 0;
}
printf("call func maxPathSum,root->val:%d,re = %d.\n",root->val,re);
int l = maxPathSum(root->left,re);
int r = maxPathSum(root->right,re);
l = (l < 0) ? 0 : l;
r = (r < 0) ? 0 : r;
if(l + r + root->val > re)
re = l + r + root->val;
int res = root->val + max(l, r);
printf("return func l:%d,r:%d,val:%d,re:%d,res:%d\n",l,r,root->val,re,res);
return res;
}
public:
int maxPathSum(TreeNode* root) {
int max = INT_MIN;
maxPathSum(root, max);
return max;
}
};
程序输出:
call func maxPathSum,root->val:-10,re = -2147483648.
call func maxPathSum,root->val:9,re = -2147483648.
call func maxPathSum,root NULL,re = -2147483648.
call func maxPathSum,root NULL,re = -2147483648.
return func l:0,r:0,val:9,re:9,res:9
call func maxPathSum,root->val:20,re = 9.
call func maxPathSum,root->val:15,re = 9.
call func maxPathSum,root NULL,re = 9.
call func maxPathSum,root NULL,re = 9.
return func l:0,r:0,val:15,re:15,res:15
call func maxPathSum,root->val:7,re = 15.
call func maxPathSum,root NULL,re = 15.
call func maxPathSum,root NULL,re = 15.
return func l:0,r:0,val:7,re:15,res:7
return func l:15,r:7,val:20,re:42,res:35
return func l:9,r:35,val:-10,re:42,res:25