[問題] Binary Tree Maximum Path Problem

[cckk3333 (皓月)]

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://www.ptt.cc/bbs/Prob_Solve/M.1397115825.A.334.html
→ flere:如果目前這點的左子樹都是負的, 那這樣會對嗎??
→ flere:沒有跑code啦單純確認一下這個caseXD 好像沒說val >= 0
→ cckk3333:我code有設定base condtion應該是沒有問題
→ cckk3333:測資沒過是時間問題 演算法應該是對的(我猜XD)
推 bleed1979:我send 10幾次終於過了。哈。
→ cckk3333:甚麼code都沒改嗎@@