Function for finding the longest path in a binary tree

Python Hard functions

Task «Function for finding the longest path in a binary tree»

Given a binary tree, each node of which contains an integer. It is necessary to find the maximum sum of values on the path from the root to a leaf. The path must start at the root and end at a leaf. Write a function `max_path_sum(root)` that takes the root of the tree and returns the maximum sum. The tree is given as a list, where -1 indicates the absence of a node. Constraints: the number of nodes is no more than 1000, node values range from -1000 to 1000.

Input Format

In the first line, an integer n — the number of nodes. In the second line, n integers separated by spaces — the values of the nodes in breadth-first traversal order (level by level), where -1 means an empty node.

Output Format

One integer — the maximum sum on the path from the root to a leaf.

Examples

Example 1

INPUT

5
-1 2 3 -1 -1

OUTPUT

2

main.py