题目：
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1/ \2 3
Return6.
题意：
求二叉树最大的路径，起点和终点都是随意的。
思路：
1.一般求这种最大路径，都是用DFS，深度优先遍历
2.如上图所示，最大路径应该为 4-5-1-6 ，以往树的递归遍历一般由根节点遍历到叶节点，然后从叶节点开始处理，然后再回溯到根节点。这里假设已经递归到3结点了，3结点没有左右结点，所以此时以3为根节点最大路径也就是一个3，然后开始回溯到5，以5为根结点的话，此时最大路径3-5-4。此时再回溯到1，发现5-3 ，5-4这两条路径只能选一条，这时候就需要做比较，谁大选谁。此时最大路径为4-5-1-6
3.用一个全局变量来获取最大路径，不断更新。
4.判断root是否为null ，是直接返回0
5.对左右结点做递归，获取以自己为根的一条从根到子结点的最长路径
6.更新最大路径值，最大路径应该为：当前结点为根节点的值+左子树最大路径的值+右子树最大路径的值
7.在这里，函数的返回值定义为以自己为根的一条从根到子结点的最长路径，这个返回值是为了提供给它的父结点计算自身的最长路径用，也就是 通过比较左右结点较大路径的值+当前节点 与 0 做比较的值。结点值可能为负，若为负值取0。
代码：
int max = 0;public int maxPathSum(TreeNode root) {if(root == null) {return 0;}max = Integer.MIN_VALUE;DFS(root);return max;}public int DFS(TreeNode root) {if(root == null) {return 0;}int leftValve = DFS(root.left);int rightValue = DFS(root.right);max = Math.max(max,root.val+leftValve+rightValue);return Math.max(0, Math.max(leftValve, rightValue)+root.val);}