image.png

我的提交

  1. class Solution {
  2. public int maxPathSum(TreeNode root) {
  3. Result result = getMaxPath(root);
  4. if (result.atLeastOne < 0) {
  5. return result.atLeastOne;
  6. }
  7. return Math.max(Math.max(result.toRoot, result.maxChild), result.atLeastOne);
  8. }
  9. public Result getMaxPath(TreeNode root) {
  10. if (root.left == null && root.right == null) {
  11. int max = Math.max(root.val, 0);
  12. return new Result(max, max, root.val);
  13. }
  14. Result left = new Result();
  15. if (root.left != null) {
  16. left = getMaxPath(root.left);
  17. }
  18. Result right = new Result();
  19. if (root.right != null) {
  20. right = getMaxPath(root.right);
  21. }
  22. int toRoot = Math.max(0, Math.max(left.toRoot, right.toRoot)) + root.val;
  23. int maxChild = Math.max(left.maxChild, right.maxChild);
  24. int maxWithRoot = root.val + left.toRoot + right.toRoot;
  25. int maxAtLeast = root.val;
  26. if (root.left != null) {
  27. maxAtLeast = Math.max(left.atLeastOne, maxAtLeast);
  28. }
  29. if (root.right != null) {
  30. maxAtLeast = Math.max(right.atLeastOne, maxAtLeast);
  31. }
  32. return new Result(toRoot, Math.max(toRoot, Math.max(maxChild, maxWithRoot)), maxAtLeast);
  33. }
  34. class Result {
  35. int toRoot;
  36. int maxChild;
  37. int atLeastOne;
  38. Result() {
  39. }
  40. Result(int a, int b, int c) {
  41. toRoot = a;
  42. maxChild = b;
  43. atLeastOne = c;
  44. }
  45. }
  46. }

首先,考虑到保存一个全局的最大路径,忘记了全局变量这个东西,蛋疼地加在了返回值中。这样,返回值除了左或右子树+root,又多了全局最大路径。

其次,没有处理好所有节点为负的情况,第一次提交时,节点全负时,我返回了0。然后不得已在返回值中又加了一个最大节点的字段,如果到最后最大节点为负,那么抛弃0答案。

官方题解

阅读了官方题解后,我意识到有全局变量,然后可以把节点全为负的情况融入最大路径字段。
于是,递归函数返回值可以是root为起点的路径了,再加一个全局最大路径变量。

  1. class Solution {
  2. int maxSum = Integer.MIN_VALUE;
  3. public int maxPathSum(TreeNode root) {
  4. getMaxWithRoot(root);
  5. return maxSum;
  6. }
  7. public int getMaxWithRoot(TreeNode root) {
  8. if (root == null) return 0;
  9. int left = Math.max(getMaxWithRoot(root.left), 0);
  10. int right = Math.max(getMaxWithRoot(root.right), 0);
  11. maxSum = Math.max(maxSum, root.val + left + right);
  12. return Math.max(left, right) + root.val;
  13. }
  14. }