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

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

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

    示例 1：
    image.png

    1. 输入：root = [1,2,3]
    2. 输出：6
    3. 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

    示例 2：
    image.png

    1. 输入：root = [-10,9,20,null,null,15,7]
    2. 输出：42
    3. 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    方法：递归

    1.    var maxSum = Int.min
    3.     func maxPathSum(root : TreeNode?) -> Int {
    4.         postOrder(root: root)
    5.         return maxSum
    6.     }
    8.     //拿到一边（左边或者右边）包括传入节点的最大路径和
    9.     func postOrder(root : TreeNode?) -> Int {
    10.         if (root == nil) {
    11.             return 0
    12.         }
    14.         let left = max(postOrder(root: root?.left), 0)
    15.         let right = max(postOrder(root: root?.right), 0)
    17.         maxSum = max(maxSum, (root!.val + left + right))
    19.         return max(root!.val + left, root!.val + right)
    20.     }