题目
给定义一个二叉树, 求二叉树的子路径的最大和.
Input: [1,2,3]
1
/ \
2 3
Output: 6
Input: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
Output: 42
思路
递归. 分别对左右子树递归.
int maxPathSumHelper(TreeNode* node, int& res) {
if (node == NULL) return 0;
int leftMax = max(maxPathSumHelper(node->left, res), 0);
int rightMax = max(maxPathSumHelper(node->right, res), 0);
res = max(res, node->val+leftMax+rightMax);
return node->val + max(leftMax,rightMax);
}
int maxPathSum(TreeNode* root) {
int res = INT_MIN;
maxPathSumHelper(root, res);
return res;
}
总结
递归求最大值, 需要理清思路. 递归程序一看就懂, 但自己写就很难.
