找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1516|回复: 5
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Binary Tree Maximum Path Sum】【二叉树】

[复制链接]

2

主题

1

精华

133

积分

资深会员

Rank: 2

积分
133
发表于 10-26-2014 11:04 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-6-2014 11:56 PM 编辑

快速通道:



题目:

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

给定一个二叉树,找到最大路径和

For example:
Given the below binary tree,

       1               
      / \   
     2   3

Return 6.

----------------------------------------------



建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)


=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================

本帖被以下淘专辑推荐:

10

主题

7

精华

367

积分

高级会员

Rank: 3Rank: 3

积分
367
发表于 11-24-2014 09:47 PM | 显示全部楼层
  1. /**
  2. post-order tranverse
  3. for each node,
  4. get the max_Path including this node, considering its left and right children
  5. and return " the max_Path including this node, and only left or right children, or only this node " to its parent

  6. Time O(n) Space O(n)
  7. **/
  8. public class Solution {
  9.     public int maxPathSum(TreeNode root) {
  10.         //valid
  11.         if(root==null) return 0;
  12.         //helper method
  13.         List<Integer> rets=new ArrayList<Integer>(1);
  14.         helper(root,rets);
  15.         if(rets.size()>0) return rets.get(0);
  16.         else return 0;
  17.         
  18.     }
  19.    
  20.     public int helper(TreeNode node, List<Integer> rets){
  21.         if(node==null) return 0;
  22.         int left=helper(node.left,rets);
  23.         int right=helper(node.right,rets);
  24.         
  25.         int ret=Math.max(node.val,Math.max(node.val+left,node.val+right));//decedents + node
  26.         int turnhere=node.val+left+right;//make a turn from this node
  27.         int maxNode=Math.max(ret,turnhere);// max path including node
  28.         if(rets.size()==0) rets.add(maxNode);
  29.         else{
  30.             maxNode=Math.max(maxNode,rets.get(0));
  31.             rets.add(0,maxNode);
  32.         }
  33.         return ret;
  34.     }
  35. }
复制代码
回复 支持 反对

使用道具 举报

10

主题

7

精华

367

积分

高级会员

Rank: 3Rank: 3

积分
367
发表于 11-24-2014 09:52 PM | 显示全部楼层
这个题为什么没有链接啊?
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表