PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Binary Tree Maximum Path Problem

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間10年前 (2014/04/11 01:17)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

※ 引述《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) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 還有dict[node.right][0] + node.val 和 dict[node.left][0] + node.val ... 我是分成三段 [2]: 結合左或結合右或node本身，相當於你的 [0] [1]: 左右子樹[0] 或左右子樹[1] 較大者 [0]: 以node為root的整棵樹，相當於node, node + 左子樹[2], node + 右子樹[2], node + 左子樹[2] + 右子樹[2] 最後比 [0] 和 [1]。問題在於當子node只有一點且是負數的情況下，[2]我會設為null。也就是如果結合會比較小，倒不如不結合，遞迴才不會出錯。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.203.156 ※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1397150236.A.D33.html