三个月算法进阶--day29
目录
float("-inf”)
子树
一个子树的内部路径，当然包含当前子树的根节点，否则就是子树的子树的内部路径。
递归反推就是由底向上，从叶子结点往上计算子树的结果值
遍历二叉树，递归或者双循环
记录
leetcode第124题二叉树中的最大路径和
class Solution:
def __init__(self):
self.ans = float("-inf")
def maxPathSum(self, root: TreeNode) -> int:
def dfs(root):
if not root:
return 0
left = max(dfs(root.left), 0)
right = max(dfs(root.right), 0)
self.ans = max(self.ans, left + root.val + right)
return root.val + max(left, right)
dfs(root)
return self.ans