题目描述：

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

  1. 输入: [1,2,3]
  3.        1
  4.       / \
  5.      2   3
  7. 输出: 6

示例 2:

  1. 输入: [-10,9,20,null,null,15,7]
  2.    -10
  3.    / \
  4.   9  20
  5.     /  \
  6.    15   7
  7. 输出: 42

算法实现：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val) {
  4.  *     this.val = val;
  5.  *     this.left = this.right = null;
  6.  * }
  7.  */
  8. /**
  9.  * @param {TreeNode} root
  10.  * @return {number}
  11.  */
  12. var maxPathSum = function(root) {
  13.     var maxVal = root.val
  14.     var getMaxVal = function(root) {
  15.         if (!root) {
  16.             return 0
  17.         }
  18.         var leftMax = getMaxVal(root.left)
  19.         var rightMax = getMaxVal(root.right)
  20.         var maxCountBoth = Math.max(root.val, root.val + leftMax, root.val + rightMax, root.val + rightMax + leftMax)
  21.         var maxCountSingle = Math.max(root.val, root.val + leftMax, root.val + rightMax)
  22.         maxVal = Math.max(maxVal,maxCountBoth)
  23.         return maxCountSingle
  24.     }
  25.     getMaxVal(root)
  26.     return maxVal
  27. };

思考：

运用递归的方法，遍历每一个节点，由底向上返回最大值。

总结：

对于val的用法还不是很熟悉，需要多练习。