我的提交
class Solution {public int maxPathSum(TreeNode root) {Result result = getMaxPath(root);if (result.atLeastOne < 0) {return result.atLeastOne;}return Math.max(Math.max(result.toRoot, result.maxChild), result.atLeastOne);}public Result getMaxPath(TreeNode root) {if (root.left == null && root.right == null) {int max = Math.max(root.val, 0);return new Result(max, max, root.val);}Result left = new Result();if (root.left != null) {left = getMaxPath(root.left);}Result right = new Result();if (root.right != null) {right = getMaxPath(root.right);}int toRoot = Math.max(0, Math.max(left.toRoot, right.toRoot)) + root.val;int maxChild = Math.max(left.maxChild, right.maxChild);int maxWithRoot = root.val + left.toRoot + right.toRoot;int maxAtLeast = root.val;if (root.left != null) {maxAtLeast = Math.max(left.atLeastOne, maxAtLeast);}if (root.right != null) {maxAtLeast = Math.max(right.atLeastOne, maxAtLeast);}return new Result(toRoot, Math.max(toRoot, Math.max(maxChild, maxWithRoot)), maxAtLeast);}class Result {int toRoot;int maxChild;int atLeastOne;Result() {}Result(int a, int b, int c) {toRoot = a;maxChild = b;atLeastOne = c;}}}
首先,考虑到保存一个全局的最大路径,忘记了全局变量这个东西,蛋疼地加在了返回值中。这样,返回值除了左或右子树+root,又多了全局最大路径。
其次,没有处理好所有节点为负的情况,第一次提交时,节点全负时,我返回了0。然后不得已在返回值中又加了一个最大节点的字段,如果到最后最大节点为负,那么抛弃0答案。
官方题解
阅读了官方题解后,我意识到有全局变量,然后可以把节点全为负的情况融入最大路径字段。
于是,递归函数返回值可以是root为起点的路径了,再加一个全局最大路径变量。
class Solution {int maxSum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {getMaxWithRoot(root);return maxSum;}public int getMaxWithRoot(TreeNode root) {if (root == null) return 0;int left = Math.max(getMaxWithRoot(root.left), 0);int right = Math.max(getMaxWithRoot(root.right), 0);maxSum = Math.max(maxSum, root.val + left + right);return Math.max(left, right) + root.val;}}
