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

题目描述

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。

同一个节点在一条路径序列中至多出现一次。

该路径至少包含一个节点，且不一定经过根节点 $root$。

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

给定一棵二叉树的根节点 $root$，请返回其最大路径和。

输入描述

输入一行若干个元素，表示二叉树的层序遍历结果。

相邻两个元素之间用一个空格隔开。

其中，整数表示节点值，$null$ 表示空节点。

输出描述

输出一个整数，表示该二叉树的最大路径和。

样例 $1$

输入

1 2 3

输出

6

样例解释

最优路径是 $2 \rightarrow 1 \rightarrow 3$。

路径和为 $2 + 1 + 3 = 6$。

样例 $2$

输入

-10 9 20 null null 15 7

输出

42

样例解释

最优路径是 $15 \rightarrow 20 \rightarrow 7$。

路径和为 $15 + 20 + 7 = 42$。

数据范围

树中节点数目范围是 $[1, 3 * 10^4]$。

$-1000 <= Node.val <= 1000$