二叉树中的最大路径和

题目描述
二叉树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。 注意: 1.同一个节点在一条二叉树路径里中最多出现一次 2.一条路径至少包含一个节点，且不一定经过根节点
给定一个二叉树的根节点root，请你计算它的最大路径和
例如： 给出以下的二叉树，
最优路径是:2=>1=>3，或者3=>1=>2，最大路径和=2+1+3=6
数据范围：节点数满足 0 <= n <= 10^5，节点上的值满足∣val∣≤1000 要求：空间复杂度 O(1)，时间复杂度 O(n) 示例1 样例： 输入 {1,2,3} 输出 6 示例2 输入 {-20,8,20,#,#,15,6} 输出 41 说明： 其中一条最大路径为:15=>20=>6，路径和为15+20+6=41 输入 {-2,#,-3} 输出 -2
题目大意
二叉树的路径就是树上某一点到另一个点路过节点的序列

二叉树中的最大路径和最先出现在Python成神之路。