No testdata at current.

题目描述

二叉树中的路径被定义为一条节点序列，序列中的每对相邻节点之间都用一条边连接。同一个节点在一条路径中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。
路径和是路径中节点值的总和。
给定一个二叉树的根节点 root，返回其最大路径和。

输入描述

以先序遍历的顺序二叉树根节点为 root = [1,2,3,4,5]。
数据范围为 ([-1000, 1000])

输出描述

则最大路径和就是 5 -> 2 -> 1 -> 3。
路径和为 (5 + 2 + 1 + 3 = 11)

样例输入输出

[1,2,3,4,5]

11

提示

假设二叉树节点数不超过 (10^5) 的情况下，如何设计你的算法使得时间复杂度达到 O(n)。