[問題] Binary Tree Maximum Path Problem

看板Prob_Solve作者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

→

flere

04/10 16:03, , 1^F

04/10 16:03, 1^F

→

flere

04/10 16:04, , 2^F

04/10 16:04, 2^F

→

cckk3333

04/10 16:20, , 3^F

04/10 16:20, 3^F