用java写二叉树取最大路径

可以通过递归实现，具体思路为：计算以每个节点为根结点的最大路径和，利用该节点的值和其左右子树的最大路径和计算出以该节点为根结点的最大路径和，最终返回整棵树的最大路径和。

以下是实现代码：

class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}

public class BinaryTreeMaxPathSum {

private int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
maxPathSumHelper(root);
return maxSum;
}

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

该代码使用了一个全局变量来记录最大路径和，maxPathSumHelper() 方法返回以该节点为根结点的最大路径和。