The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1 / \ 2 3Return
6
.解题思路:
1. 对于任何一个node, 有四种path情况需要考虑:
1.1 仅有node
1.2 左子树+node
1.3 node + 右子树
1.4 左子树 + node + 右子树
为了求最大的path sum. 我们需要从1-3中选出最大的返回给parent,从1-4中选出最大的作为备选的最后结果path sum.
Java Code:
public int maxPathSum(TreeNode root){ int[] max = new int[1]; max[0] = Integer.MIN_VALUE; maxSum(root, max); return max[0]; } public int maxSum(TreeNode root, int[] max){ int val = 0, left = 0, right = 0; val = root != null ? root.val : 0; left = root.left != null? maxSum(root.left, max) : 0; right = root.right != null ? maxSum(root.right, max) : 0; int currMax = val; if(left > 0) currMax += left; if(right > 0) currMax += right; max[0] = max[0] > currMax? max[0] : currMax; if(left > 0 && left >= right) return val + left; if(right > 0 && right > left) return val + right; return val; }
No comments:
Post a Comment