题目描述 二叉树中的路径是一个结点序列，序列中每对相邻结点之间都有一条边，同一结点在一条路径中至多出现一次。路径至少包含一个结点，并且不一定经过根结点。 路径和为路径上所有结点值之和。给定一棵非空二叉树，求其最大路径和。 输入格式 第一行输入整数 $k$，表示二叉树层序序列中的记号数。 第二行输入 $k$ 个以空格分隔的记号。整数表示一个结点的值，null 表示空位置。对于每个非空结点，按从左到右的顺序依次读取其左、右孩子；序列省略末尾无意义的 null。 输出格式 输出一个整数，表示二叉树的最大路径和。 数据范围 $1\le n\le 3\times 10^4$，其中 $n$ 为树中结点数 $-1000\le \text{Node.val}\le 1000$ $1\le k\le 2n+1$ 输入保证层序序列合法且根记号不是 null。 输入样例 7 -10 9 20 null null 15 7 输出样例 42