题解 | #二叉树的最大路径和#
二叉树的最大路径和
http://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { private int max; /** * * @param root TreeNode类 * @return int整型 */ public int maxPathSum (TreeNode root) { // write code here max = Integer.MIN_VALUE; maxPathDown(root); return max; } private int maxPathDown(TreeNode node) { if (node == null) return 0; int left = Math.max(0,maxPathDown(node.left)); int right = Math.max(0,maxPathDown(node.right)); max = Math.max(max,left + right + node.val); return Math.max(left,right) + node.val; } }