※ 引述《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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1397150236.A.D33.html