题目

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

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

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

示例1：
输入：root = [1, 2, 3]
输出：6
代码:

  1.   /**
  2.      * 剑指offer解法
  3.      * @param root
  4.      * @param maxSum
  5.      * @return
  6.      */
  7.     public int getMaxCount(TreeNode<Integer> root,int[] maxSum){
  8.         if(root==null){
  9.             return 0;
  10.         }
  11.         int[] maxSumLeft={Integer.MIN_VALUE};
  12.         int left=Math.max(0,getMaxCount(root.lTreeNode,maxSumLeft));
  13.         int[] maxSumRight={Integer.MIN_VALUE};
  14.         int right=Math.max(0,getMaxCount(root.rTreeNode,maxSumRight));
  15.         maxSum[0] = Math.max(maxSumLeft[0], maxSumRight[0]);
  16.         maxSum[0]=Math.max(maxSum[0], root.data+left+right);
  17.         int s=root.data+Math.max(left,right);
  18.        return s;
  19.     }
  21.       public int maxPathSum(TreeNode<Integer> root){
  22.         int[] maxSum={Integer.MIN_VALUE};
  23.         getMaxCount(root,maxSum);
  24.         return maxSum[0];
  25.     }