FilesExpand file tree

 master

/

BinaryTreeMaximumPathSum.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

54 lines (44 loc) · 1.2 KB

 master

/

BinaryTreeMaximumPathSum.java

Copy path

Top

File metadata and controls

• Code
• Blame

54 lines (44 loc) · 1.2 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

51

52

53

54

package leetcode;

/**

* Project Name : Leetcode

* Package Name : leetcode

* File Name : BinaryTreeMaximumPathSum

* Creator : Edward

* Date : Nov, 2017

* Description : 124. Binary Tree Maximum Path Sum

*/

public class BinaryTreeMaximumPathSum {

/**

* 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.

3

/ \

9 20

/ \

15 7

time : O(n)

space : O(n)

*/

int res;

public int maxPathSum(TreeNode root) {

if (root == null) return 0;

res = Integer.MIN_VALUE;

helper(root);

return res;

}

public int helper(TreeNode root) {

if (root == null) return 0;

int left = Math.max(0, helper(root.left));

int right = Math.max(0, helper(root.right));

res = Math.max(res, left + right + root.val);

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

}

}