FilesExpand file tree

 master

/

BinaryTreeMaximumPathSum.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

62 lines (56 loc) · 1.67 KB

 master

/

BinaryTreeMaximumPathSum.java

Copy path

Top

File metadata and controls

• Code
• Blame

62 lines (56 loc) · 1.67 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

55

56

57

58

59

60

61

62

package tree;

/**

* Created by gouthamvidyapradhan on 03/04/2017. Given a binary tree, find the maximum path sum.

*

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

*

* <p>For example: Given the below binary tree,

*

* <p>1 / \ 2 3 Return 6.

*/

public class BinaryTreeMaximumPathSum {

public static class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

}

}

private int max = Integer.MIN_VALUE;

/**

* Main method

*

* @param args

* @throws Exception

*/

public static void main(String[] args) throws Exception {

TreeNode root = new TreeNode(5);

root.left = new TreeNode(4);

root.left.left = new TreeNode(3);

root.left.left.left = new TreeNode(-1);

root.right = new TreeNode(7);

root.right.left = new TreeNode(2);

root.right.left.left = new TreeNode(9);

System.out.println(new BinaryTreeMaximumPathSum().maxPathSum(root));

}

public int maxPathSum(TreeNode root) {

if (root == null) return 0;

dfs(root);

return max;

}

private int dfs(TreeNode root) {

if (root == null) return 0;

int left = dfs(root.left);

int right = dfs(root.right);

max = Math.max(max, root.val);

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

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

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

int leftVal = Math.max(root.val, root.val + left);

int rightVal = Math.max(root.val, root.val + right);

return Math.max(leftVal, rightVal);

}

}