作者cckk3333 (皓月)
看板Prob_Solve
标题[问题] Binary Tree Maximum Path Problem
时间Thu Apr 10 15:43:42 2014
leetcode的题目
----------------------------------------------------------
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
----------------------------------------------------------
基本上我是用DP的方法 bottom-up
树上每ㄧ点纪录两个数值
(1) 以这点为 root 的 sub-tree，找出从 root 到 subtree 中 node 路径总合的最大值
(2) 以这点为 root 的 sub-tree 的 maximum path sum
然後用递回
dict[node][0] =
max(dict[node.left][0] + node.val, dict[node.right][0] + node.val, node.val )
dict[node][1] =
max(dict[node.left][1], dict[node.right][1], dict[node.left][0] +
dict[node.right][0] + node.val)
----------------------------------------------------------
以下是我的 code
https://dl.dropboxusercontent.com/u/43614743/code.py
----------------------------------------------------------
计算ㄧ下应该是O(n) n : #nodes
解法也跟网路上大部分的方法差不多
但就是过不了测资
求解@@
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.111.64.38
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1397115825.A.334.html
1F：→ flere:如果目前这点的左子树都是负的, 那这样会对吗?? 04/10 16:03
2F：→ flere:没有跑code啦单纯确认一下这个caseXD 好像没说val >= 0 04/10 16:04
3F：→ cckk3333:我code有设定base condtion应该是没有问题 04/10 16:20
4F：→ cckk3333:测资没过是时间问题 演算法应该是对的(我猜XD) 04/10 16:21
5F：推 bleed1979:我send 10几次终於过了。哈。 04/11 00:39
6F：→ cckk3333:甚麽code都没改吗@@ 04/11 08:27