0124_binary-tree-maximum-path-sum

README

0124_binary-tree-maximum-path-sum

递归, 后序遍历(post-order traversal).

在不考虑元素为负的情况下, 我们需要左右子树返回:

• 左右子树对于问题的答案
• 左右子树的从根到叶的最大和

当前子树的答案是以下三个值的最大值:

• 左右子树对于问题的答案
• 左右子树的从根到叶的最大和的和, 加上根节点的值

当前子树的从根到叶的最大和就是以下两个值的最大值:

• 左子树的从根到叶的最大和, 加上根节点的值
• 右子树的从根到叶的最大和, 加上根节点的值

---

考虑元素为负的情况下, 我们需要左右子树返回::

• 左右子树对于问题的答案
• 左子树从根到某一点的最大和
• 右子树从根到某一点的最大和

计算策略出现了变更.

当前子树的答案是以下三个值的最大值:

• 左右子树对于问题的答案(注意空节点没有答案)
• 左右子树的从根到某一点的最大和的和, 需要判是否抛弃(<0时视作0), 加上根节点的值

当前子树的从根到某一点的最大和就是以下三个值的最大值:

• 左子树的从根到某一点的最大和, 加上根节点的值
• 右子树的从根到某一点的最大和, 加上根节点的值
• 根节点自己的值

联动

0543_diameter-of-binary-tree