LeetCode124—Binary Tree Maximum Path Sum

Love The Way You Lie 2022-08-21 10:59 43阅读 0赞

LeetCode124—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. 1
  2. / \
  3. 2 3

Return 6.

分析

参考:http://blog.csdn.net/linhuanmars/article/details/22969069
这题确实有点难,刚开始以为树的深度遍历序列中找到和最大子序列,这样进行一次深度优先搜索将结果存在数组中,在对数组做一次最大子序列和运算(考虑节点值可能有负数),然而题目的要求并不是这样的。

题目要求是:要在树中找一条连通的通路,其值最大

对于树中的某个节点来说,需要考虑两件事情:1是记录到该节点时权值是多少(并实时更新最大值),2是记录经过这个节点的路径来自于左孩子还是右孩子,这两件事情一定要分别计算,最大值要算上左右孩子,但是路径只能是左孩子或者右孩子的其中之一。

代码

  1. class Solution {
  2. int dfs(TreeNode* root,int &maxSum)
  3. {
  4. if (root == NULL)
  5. return 0;
  6. int left = dfs(root->left,maxSum);
  7. int right = dfs(root->right,maxSum);
  8. int rootval = root->val + max(0, left) + max(0,right);
  9. if (maxSum < rootval)
  10. maxSum = rootval;
  11. // return rootval;
  12. return root->val + max(max(left,right),0);
  13. }
  14. public:
  15. int maxPathSum(TreeNode* root) {
  16. int maxSum = root->val;
  17. dfs(root,maxSum);
  18. return maxSum;
  19. }
  20. };

发表评论

表情:
评论列表 (有 0 条评论,43人围观)

还没有评论,来说两句吧...

相关阅读