二叉树中的最大路径和:递归找贡献值

题目

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

链接

124. 二叉树中的最大路径和

思考

这道题目怎么做?先讲讲基础的理论,我们拼子链,然后适当的拐弯是不是就能遍历找到合适的?负的不去,然后找左右较大的加,好简陋啊,就是一个节点判断左右两边,找大的那边加上然后返回给父级判断怎么接最大

代码

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def maxPathSum(self, root):
        self.max_num = float('-inf')

        def dfs(node):
            if not node:
                return 0

            left = dfs(node.left)
            right = dfs(node.right)

            current_num = node.val + max(right,0) + max(left,0)
            self.max_num = max(current_num,self.max_num)

            return node.val + max(right,left,0)

        dfs(root)
        return self.max_num

‍