二叉树中的最大路径和

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

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

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

输入

• root：二叉树根节点，用力扣层序数组表示

输出

最大路径和（整数）。

示例一

输入：

root = [1, 2, 3]

输出：

6

解释：路径 2 -> 1 -> 3，和为 6。

示例二

输入：

root = [-10, 9, 20, null, null, 15, 7]

输出：

42

解释：路径 15 -> 20 -> 7，和为 42。

示例三

输入：

root = [-3]

输出：

-3