函数用于在二叉树中查找最长路径

Python Hard functions

任务 «函数用于在二叉树中查找最长路径»

给定一个二叉树，每个节点包含一个整数。需要找到从根节点到叶子节点的路径上的最大数值总和。路径必须从根节点开始，到叶子节点结束。请编写函数 max_path_sum(root)，该函数接收树的根节点并返回最大总和。树以列表形式给出，其中 -1 表示节点不存在。限制条件：节点数量不超过 1000，节点数值范围为 -1000 到 1000。

输入格式

在第一行中，整数 n 表示节点数量。在第二行中，有 n 个以空格分隔的整数，表示按广度优先遍历（逐层）的节点值，其中 -1 表示空节点。

输出格式

一个整数——从根节点到叶子节点的路径上的最大和。

示例

示例 1

输入

5
-1 2 3 -1 -1

输出

2

main.py