題目
給定義一個二叉樹, 求二叉樹的子路徑的最大和.
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;
}
總結(jié)
遞歸求最大值, 需要理清思路. 遞歸程序一看就懂, 但自己寫就很難.
