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

Return 6.

原题链接：https://oj.leetcode.com/problems/binary-tree-maximum-path-sum/

题目：给定一二叉树，求出最大路径和。

分析：分别求出左右子树的最大路径和，同根节点的值相加。

	int max = 0;
	public int maxPathSum(TreeNode root) {
		max = (root == null) ? 0 : root.val;
		max(root);
		return max;
	}

	public int max(TreeNode node) {
		if (node == null)
			return 0;
		int left = Math.max(0, max(node.left));
		int right = Math.max(0, max(node.right));
		max = Math.max(node.val + left + right, max);
		return node.val + Math.max(left, right);
	}

	// Definition for binary tree
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

LeetCode——Binary Tree Maximum Path Sum