二叉树中的最大路径和
Last updated
Last updated
问题简述
思路:树形DP
考虑对以 X 为头结点的树,为了求得最大路径和,需要从左右子树获取哪些信息?
根据要求,显然需要知道:
子树能提供的最大和路径,即以子树节点为终点的最大路径,记 h: int
;
为什么需要这个信息:为了计算经过 X 节点的最大路径,这条路径的特点是:从某一节点出发到达子树节点,经过 X 节点后,再进入另一个子节点的最大和路径;
这是本题除 coding 外最大的难点,能想出这个信息也就基本解决这个问题了;
子树中的最大路径和(即子问题):为了比较得出全局最大路径和,记 s: int
;
假设子树的这些信息已知,怎么求 X 节点的上述信息:
x_h = x.val + max(0, l.h, r.h)
因为需要经过 X 节点,所以必须加上 x.val,同时如果左右子树提供的 h 小于 0,那么不如舍去;
x_s = max(l.s, r.s, max(l.h, 0) + max(r.h, 0) + x.val)
这一步容易写成
x_s = max(l.s, r.s, x_h)
或者x_s = max(l.s, r.s, l.h + r.h + x.val)
,都是对问题理解不到位;
重申:模板只是帮我们解决怎么组织代码的问题,而写出正确的代码一靠观察,二靠积累;
对空节点,有: