P4067.二叉树中的最大路径和
LeetCode 124. 二叉树中的最大路径和
题目描述
二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。
同一个节点在一条路径序列中至多出现一次。
该路径至少包含一个节点，且不一定经过根节点 root。
路径和是路径中各节点值的总和。
给定一棵二叉树的根节点 root，请返回其最大路径和。
输入描述
输入一行若干个元素，表示二叉树的层序遍历结果。
相邻两个元素之间用一个空格隔开。
其中，整数表示节点值，null 表示空节点。
输出描述
输出一个整数，表示该二叉树的最大路径和。
样例 1
输入
1 2 3
输出
6
样例解释
最优路径是 2→1→3。
路径和为 2+1+3=6。
样例 2
输入
-10 9 20 null null 15 7
输出
42
样例解释
最优路径是 15→20→7。
路径和为 15+20+7=42。
数据范围
树中节点数目范围是 [1,3∗104]。
−1000<=Node.val<=1000
