FilesExpand file tree

 master

/

BinaryTreeMaximumPathSum.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

50 lines (48 loc) · 1.35 KB

 master

/

BinaryTreeMaximumPathSum.java

Top

File metadata and controls

• Code
• Blame

50 lines (48 loc) · 1.35 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

44

45

46

47

48

49

50

/**

* Given a binary tree, find the maximum path sum.

*

* The path may start and end at any node in the tree.

*

* For example: Given the below binary tree,

*

* 1

* / \

* 2 3

*

* Return 6.

*

*/

public class BinaryTreeMaximumPathSum {

public int maxPathSum(TreeNode root) {

if (root == null)

return 0;

int[] max = new int[1];

max[0] = Integer.MIN_VALUE;

maxPathSum(root, max);

return max[0];

}

private int maxPathSum(TreeNode root, int[] max) {

if (root.left == null && root.right == null) {

max[0] = root.val > max[0] ? root.val : max[0];

return root.val;

} else if (root.left != null && root.right == null) {

int left = maxPathSum(root.left, max);

max[0] = left > 0 ? Math.max(left + root.val, max[0]) : Math.max(

root.val, max[0]);

return left > 0 ? left + root.val : root.val;

} else if (root.left == null && root.right != null) {

int right = maxPathSum(root.right, max);

max[0] = right > 0 ? Math.max(right + root.val, max[0]) : Math.max(

root.val, max[0]);

return right > 0 ? right + root.val : root.val;

} else {

int left = maxPathSum(root.left, max);

int right = maxPathSum(root.right, max);

int tmp = root.val;

tmp += left > 0 ? left : 0;

tmp += right > 0 ? right : 0;

max[0] = tmp > max[0] ? tmp : max[0];

return Math.max(Math.max(left, right), 0) + root.val;

}

}

}