算法学习笔记 —— 排序

学而时习，本文记录排序操作相关算法练习笔记。

二叉树中的最大路径和

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

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

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    res = float("-inf")
    def maxPathSum(self, root: Optional[TreeNode]) -> int:

        def max_sum_route(node):
            if node is None:
                return 0

            left_max = max(0, max_sum_route(node.left))
            right_max = max(0, max_sum_route(node.right))

            if left_max + right_max + node.val > self.res:
                self.res = left_max + right_max + node.val
            cur_max_val = max(0, node.val, node.val + left_max, node.val + right_max)
            return cur_max_val
        max_sum_route(root)
        return self.res
            

文章链接：
https://www.zywvvd.com/notes/study/algorithm/tree/about-tree/