leetcode/BinaryTreeMaximumPathSum.java at master · mengli/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Given a binary tree, find the maximum path sum.
 *
 * <p>The path may start and end at any node in the tree.
 *
 * <p>For example: Given the below binary tree,
 *
 * <p>1 / \ 2 3
 *
 * <p>Return 6.
 */
publicclassBinaryTreeMaximumPathSum {
publicintmaxPathSum(TreeNoderoot) {
if (root == null) return0;
int[] max = newint[1];
max[0] = Integer.MIN_VALUE;
maxPathSum(root, max);
returnmax[0];
 }

privateintmaxPathSum(TreeNoderoot, int[] max) {
if (root.left == null && root.right == null) {
max[0] = root.val > max[0] ? root.val : max[0];
returnroot.val;
 } elseif (root.left != null && root.right == null) {
intleft = maxPathSum(root.left, max);
max[0] = left > 0 ? Math.max(left + root.val, max[0]) : Math.max(root.val, max[0]);
returnleft > 0 ? left + root.val : root.val;
 } elseif (root.left == null && root.right != null) {
intright = maxPathSum(root.right, max);
max[0] = right > 0 ? Math.max(right + root.val, max[0]) : Math.max(root.val, max[0]);
returnright > 0 ? right + root.val : root.val;
 } else {
intleft = maxPathSum(root.left, max);
intright = maxPathSum(root.right, max);
inttmp = root.val;
tmp += left > 0 ? left : 0;
tmp += right > 0 ? right : 0;
max[0] = tmp > max[0] ? tmp : max[0];
returnMath.max(Math.max(left, right), 0) + root.val;
 }
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Given a binary tree, find the maximum path sum.
 *
 * <p>The path may start and end at any node in the tree.
 *
 * <p>For example: Given the below binary tree,
 *
 * <p>1 / \ 2 3
 *
 * <p>Return 6.
 */
publicclassBinaryTreeMaximumPathSum {
publicintmaxPathSum(TreeNoderoot) {
if (root == null) return0;
int[] max = newint[1];
max[0] = Integer.MIN_VALUE;
maxPathSum(root, max);
returnmax[0];
 }

privateintmaxPathSum(TreeNoderoot, int[] max) {
if (root.left == null && root.right == null) {
max[0] = root.val > max[0] ? root.val : max[0];
returnroot.val;
 } elseif (root.left != null && root.right == null) {
intleft = maxPathSum(root.left, max);
max[0] = left > 0 ? Math.max(left + root.val, max[0]) : Math.max(root.val, max[0]);
returnleft > 0 ? left + root.val : root.val;
 } elseif (root.left == null && root.right != null) {
intright = maxPathSum(root.right, max);
max[0] = right > 0 ? Math.max(right + root.val, max[0]) : Math.max(root.val, max[0]);
returnright > 0 ? right + root.val : root.val;
 } else {
intleft = maxPathSum(root.left, max);
intright = maxPathSum(root.right, max);
inttmp = root.val;
tmp += left > 0 ? left : 0;
tmp += right > 0 ? right : 0;
max[0] = tmp > max[0] ? tmp : max[0];
returnMath.max(Math.max(left, right), 0) + root.val;
 }
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Given a binary tree, find the maximum path sum.
 *
 * <p>The path may start and end at any node in the tree.
 *
 * <p>For example: Given the below binary tree,
 *
 * <p>1 / \ 2 3
 *
 * <p>Return 6.
 */
publicclassBinaryTreeMaximumPathSum {
publicintmaxPathSum(TreeNoderoot) {
if (root == null) return0;
int[] max = newint[1];
max[0] = Integer.MIN_VALUE;
maxPathSum(root, max);
returnmax[0];
 }

privateintmaxPathSum(TreeNoderoot, int[] max) {
if (root.left == null && root.right == null) {
max[0] = root.val > max[0] ? root.val : max[0];
returnroot.val;
 } elseif (root.left != null && root.right == null) {
intleft = maxPathSum(root.left, max);
max[0] = left > 0 ? Math.max(left + root.val, max[0]) : Math.max(root.val, max[0]);
returnleft > 0 ? left + root.val : root.val;
 } elseif (root.left == null && root.right != null) {
intright = maxPathSum(root.right, max);
max[0] = right > 0 ? Math.max(right + root.val, max[0]) : Math.max(root.val, max[0]);
returnright > 0 ? right + root.val : root.val;
 } else {
intleft = maxPathSum(root.left, max);
intright = maxPathSum(root.right, max);
inttmp = root.val;
tmp += left > 0 ? left : 0;
tmp += right > 0 ? right : 0;
max[0] = tmp > max[0] ? tmp : max[0];
returnMath.max(Math.max(left, right), 0) + root.val;
 }
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Given a binary tree, find the maximum path sum.
 *
 * <p>The path may start and end at any node in the tree.
 *
 * <p>For example: Given the below binary tree,
 *
 * <p>1 / \ 2 3
 *
 * <p>Return 6.
 */
publicclassBinaryTreeMaximumPathSum {
publicintmaxPathSum(TreeNoderoot) {
if (root == null) return0;
int[] max = newint[1];
max[0] = Integer.MIN_VALUE;
maxPathSum(root, max);
returnmax[0];
 }

privateintmaxPathSum(TreeNoderoot, int[] max) {
if (root.left == null && root.right == null) {
max[0] = root.val > max[0] ? root.val : max[0];
returnroot.val;
 } elseif (root.left != null && root.right == null) {
intleft = maxPathSum(root.left, max);
max[0] = left > 0 ? Math.max(left + root.val, max[0]) : Math.max(root.val, max[0]);
returnleft > 0 ? left + root.val : root.val;
 } elseif (root.left == null && root.right != null) {
intright = maxPathSum(root.right, max);
max[0] = right > 0 ? Math.max(right + root.val, max[0]) : Math.max(root.val, max[0]);
returnright > 0 ? right + root.val : root.val;
 } else {
intleft = maxPathSum(root.left, max);
intright = maxPathSum(root.right, max);
inttmp = root.val;
tmp += left > 0 ? left : 0;
tmp += right > 0 ? right : 0;
max[0] = tmp > max[0] ? tmp : max[0];
returnMath.max(Math.max(left, right), 0) + root.val;
 }
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Given a binary tree, find the maximum path sum.
 *
 * <p>The path may start and end at any node in the tree.
 *
 * <p>For example: Given the below binary tree,
 *
 * <p>1 / \ 2 3
 *
 * <p>Return 6.
 */
publicclassBinaryTreeMaximumPathSum {
publicintmaxPathSum(TreeNoderoot) {
if (root == null) return0;
int[] max = newint[1];
max[0] = Integer.MIN_VALUE;
maxPathSum(root, max);
returnmax[0];
 }

privateintmaxPathSum(TreeNoderoot, int[] max) {
if (root.left == null && root.right == null) {
max[0] = root.val > max[0] ? root.val : max[0];
returnroot.val;
 } elseif (root.left != null && root.right == null) {
intleft = maxPathSum(root.left, max);
max[0] = left > 0 ? Math.max(left + root.val, max[0]) : Math.max(root.val, max[0]);
returnleft > 0 ? left + root.val : root.val;
 } elseif (root.left == null && root.right != null) {
intright = maxPathSum(root.right, max);
max[0] = right > 0 ? Math.max(right + root.val, max[0]) : Math.max(root.val, max[0]);
returnright > 0 ? right + root.val : root.val;
 } else {
intleft = maxPathSum(root.left, max);
intright = maxPathSum(root.right, max);
inttmp = root.val;
tmp += left > 0 ? left : 0;
tmp += right > 0 ? right : 0;
max[0] = tmp > max[0] ? tmp : max[0];
returnMath.max(Math.max(left, right), 0) + root.val;
 }
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Given a binary tree, find the maximum path sum.
 *
 * <p>The path may start and end at any node in the tree.
 *
 * <p>For example: Given the below binary tree,
 *
 * <p>1 / \ 2 3
 *
 * <p>Return 6.
 */
publicclassBinaryTreeMaximumPathSum {
publicintmaxPathSum(TreeNoderoot) {
if (root == null) return0;
int[] max = newint[1];
max[0] = Integer.MIN_VALUE;
maxPathSum(root, max);
returnmax[0];
 }

privateintmaxPathSum(TreeNoderoot, int[] max) {
if (root.left == null && root.right == null) {
max[0] = root.val > max[0] ? root.val : max[0];
returnroot.val;
 } elseif (root.left != null && root.right == null) {
intleft = maxPathSum(root.left, max);
max[0] = left > 0 ? Math.max(left + root.val, max[0]) : Math.max(root.val, max[0]);
returnleft > 0 ? left + root.val : root.val;
 } elseif (root.left == null && root.right != null) {
intright = maxPathSum(root.right, max);
max[0] = right > 0 ? Math.max(right + root.val, max[0]) : Math.max(root.val, max[0]);
returnright > 0 ? right + root.val : root.val;
 } else {
intleft = maxPathSum(root.left, max);
intright = maxPathSum(root.right, max);
inttmp = root.val;
tmp += left > 0 ? left : 0;
tmp += right > 0 ? right : 0;
max[0] = tmp > max[0] ? tmp : max[0];
returnMath.max(Math.max(left, right), 0) + root.val;
 }
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Given a binary tree, find the maximum path sum.
 *
 * <p>The path may start and end at any node in the tree.
 *
 * <p>For example: Given the below binary tree,
 *
 * <p>1 / \ 2 3
 *
 * <p>Return 6.
 */
publicclassBinaryTreeMaximumPathSum {
publicintmaxPathSum(TreeNoderoot) {
if (root == null) return0;
int[] max = newint[1];
max[0] = Integer.MIN_VALUE;
maxPathSum(root, max);
returnmax[0];
 }

privateintmaxPathSum(TreeNoderoot, int[] max) {
if (root.left == null && root.right == null) {
max[0] = root.val > max[0] ? root.val : max[0];
returnroot.val;
 } elseif (root.left != null && root.right == null) {
intleft = maxPathSum(root.left, max);
max[0] = left > 0 ? Math.max(left + root.val, max[0]) : Math.max(root.val, max[0]);
returnleft > 0 ? left + root.val : root.val;
 } elseif (root.left == null && root.right != null) {
intright = maxPathSum(root.right, max);
max[0] = right > 0 ? Math.max(right + root.val, max[0]) : Math.max(root.val, max[0]);
returnright > 0 ? right + root.val : root.val;
 } else {
intleft = maxPathSum(root.left, max);
intright = maxPathSum(root.right, max);
inttmp = root.val;
tmp += left > 0 ? left : 0;
tmp += right > 0 ? right : 0;
max[0] = tmp > max[0] ? tmp : max[0];
returnMath.max(Math.max(left, right), 0) + root.val;
 }
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Given a binary tree, find the maximum path sum.
 *
 * <p>The path may start and end at any node in the tree.
 *
 * <p>For example: Given the below binary tree,
 *
 * <p>1 / \ 2 3
 *
 * <p>Return 6.
 */
publicclassBinaryTreeMaximumPathSum {
publicintmaxPathSum(TreeNoderoot) {
if (root == null) return0;
int[] max = newint[1];
max[0] = Integer.MIN_VALUE;
maxPathSum(root, max);
returnmax[0];
 }

privateintmaxPathSum(TreeNoderoot, int[] max) {
if (root.left == null && root.right == null) {
max[0] = root.val > max[0] ? root.val : max[0];
returnroot.val;
 } elseif (root.left != null && root.right == null) {
intleft = maxPathSum(root.left, max);
max[0] = left > 0 ? Math.max(left + root.val, max[0]) : Math.max(root.val, max[0]);
returnleft > 0 ? left + root.val : root.val;
 } elseif (root.left == null && root.right != null) {
intright = maxPathSum(root.right, max);
max[0] = right > 0 ? Math.max(right + root.val, max[0]) : Math.max(root.val, max[0]);
returnright > 0 ? right + root.val : root.val;
 } else {
intleft = maxPathSum(root.left, max);
intright = maxPathSum(root.right, max);
inttmp = root.val;
tmp += left > 0 ? left : 0;
tmp += right > 0 ? right : 0;
max[0] = tmp > max[0] ? tmp : max[0];
returnMath.max(Math.max(left, right), 0) + root.val;
 }
 }
}