Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
For example:
Given the below binary tree,
1
/ |
2 3
Return 6.
題意：求一個二叉樹的一條最大路徑和昂勉，這條路徑可以從任意節(jié)點起始掺栅，到任意節(jié)點結束陶珠，但至少要有一個節(jié)點践美。
思路：
如例子，路徑總共有三種類型：[1,2]，[1,3]，[2,1,3]。
即每個節(jié)點可以連接它的左邊一條最大路徑肩袍，或連接右邊一條最大路徑，或把左右最大路徑連接起來婚惫。
因此我想到氛赐，用一個方法求以當前節(jié)點為起始節(jié)點，到它下方任意節(jié)點為終點的最長路徑先舷。通過這個方法可以求一個節(jié)點左右的最長路徑和艰管，然后和這個節(jié)點值相加，就是以這個節(jié)點作為頂點的最大路徑蒋川。遍歷樹中所有節(jié)點牲芋，就可以找到最大的路徑和。
public int maxPath = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
int left = helper(cur.left);
int right = helper(cur.right);
maxPath = Math.max(maxPath, left + cur.val + right);
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
return maxPath;
}
public int helper(TreeNode root) {
if (root == null) {
return 0;
}
int left = helper(root.left);
int right = helper(root.right);
int curMax = Math.max(left, right) + root.val;
return curMax > 0 ? curMax : 0;
}
這個方法，可以通過缸浦，但是會超時夕冲。原因是每層都遍歷一次，那么樹下方的節(jié)點要重復調用helper很多次裂逐。
優(yōu)化：helper中已經(jīng)得到了一個節(jié)點左右單向最大路徑和歹鱼，那么就可以在helper中直接求出以當前節(jié)點為頂點的最大路徑和。即把maxPath更新的那行代碼移到helper中卜高，這樣每個節(jié)點只會被遍歷一次弥姻。
public int maxPath = Integer.MIN_VALUE;
public int maxPathSum1(TreeNode root) {
if (root == null) {
return 0;
}
helper(root);
return maxPath;
}
public int helper1(TreeNode root) {
if (root == null) {
return 0;
}
int left = helper(root.left);
int right = helper(root.right);
maxPath = Math.max(maxPath, root.val + left + right);
int curMax = Math.max(left, right) + root.val;
return curMax > 0 ? curMax : 0;
}