首页 > 其他 > 详细

Binary Tree Maximum Path Sum 自底向上求解(重重重重)

时间:2017-07-09 11:47:30      阅读:155      评论:0      收藏:0      [点我收藏+]

题目:

链接

解答:

自底向上求解。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;
	 }

 };


Binary Tree Maximum Path Sum 自底向上求解(重重重重)

原文:http://www.cnblogs.com/mthoutai/p/7140755.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!