124. Binary Tree Maximum Path Sum

Given a 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 does not need to go through the root.

For example:
Given the below binary tree,

       1
/ \
2 3

Return 6.

=============

题目:树中联通路径中,路径元素和最大值?

路径利用父子关系相连,不必经过根节点root

路径可以从任意节点开始,到任意节点.

=====

思路:

这道题的解法,来自网络leetcode150题集合,

利用dfs遍历树的方式,传递每个树父子节点间的路径大小;

利用一个全局遍历来时记住max_sum来记录已经找到的最大的路径值,

最难理解的是怎么在 dfs遍历树的过程,传递路径信息?

-----

借用"最大连续子序列和"问题的思路,array只有一个方向,

但是Tree有左右两个方向,我们需要比较两个方向上的值.

先算出左右子树的结果L和R.

  如果L>0,那么对后序结果是有利的,后序中加上L,(不是向max_sum中,而是向如节点中)

  如果R>0,那么对后序结果是有利的,加上R

---

==========

代码如下:

/**
* 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 {
public:
///
int help_maxPathSum(int &max_sum,TreeNode *root){
if(root==nullptr) return ;
int l = help_maxPathSum(max_sum,root->left);
int r = help_maxPathSum(max_sum,root->right);
int sum = root->val;
if(l>) sum += l;
if(r>) sum += r;
max_sum = max(max_sum,sum);
return max(r,l)>? max(r,l)+root->val:root->val;//只能向上传递 左子树或者 右子树的有利值
}
int maxPathSum(TreeNode* root) {
int max_sum = INT_MIN;
help_maxPathSum(max_sum,root);
return max_sum;
}
};
上一篇:Qt5该插件机制(7)--插件开发演示示例代码(Lower-level API)


下一篇:并不对劲的bzoj3994:loj2185:p3327[SDOI2015]约数个数和