[問題] Binary Tree Maximum Path Problem
看板Prob_Solve (計算數學 Problem Solving)作者cckk3333 (皓月)時間10年前 (2014/04/10 15:43)推噓1(1推 0噓 5→)留言6則, 3人參與討論串1/2 (看更多)
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
→
04/10 16:03, , 1F
04/10 16:03, 1F
→
04/10 16:04, , 2F
04/10 16:04, 2F
→
04/10 16:20, , 3F
04/10 16:20, 3F
→
04/10 16:21, , 4F
04/10 16:21, 4F
推
04/11 00:39, , 5F
04/11 00:39, 5F
→
04/11 08:27, , 6F
04/11 08:27, 6F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
