首页 > 代码库 > Binary Tree Maximum Path Sum 自底向上求解(重重重)
Binary Tree Maximum Path Sum 自底向上求解(重重重)
题目:
链接
解答:
自底向上求解。left_max right_max分别返回了左右子树的最大路径和,如果左右子树最大路径和小于0,那么返回零, 用这个最大路径和和根节点的值相加,来更新最大值,同时, 更新返回该树的最大路径值。
代码:
class Solution { public: int max = INT_MIN; int maxPathSum(TreeNode *root) { if (root == NULL) return 0; search(root); return max; } int search(TreeNode *root) { if (root == NULL) return 0; int left_max = search(root->left); int right_max = search(root->right); int sum = left_max + right_max + root->val; if (sum > max) max = sum; sum = left_max > right_max ? left_max + root->val : right_max + root->val; if (sum > 0) return sum; return 0; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。