FilesExpand file tree

 master

/

DiameterOfBinaryTree.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

54 lines (48 loc) · 1.32 KB

 master

/

DiameterOfBinaryTree.java

Copy path

Top

File metadata and controls

• Code
• Blame

54 lines (48 loc) · 1.32 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 tree;

/**

* Created by gouthamvidyapradhan on 18/10/2017.

*

* <p>Given a binary tree, you need to compute the length of the diameter of the tree. The diameter

* of a binary tree is the length of the longest path between any two nodes in a tree. This path may

* or may not pass through the root.

*

* <p>Example: Given a binary tree 1 / \ 2 3 / \ 4 5 Return 3, which is the length of the path

* [4,2,1,3] or [5,2,1,3].

*

* <p>Note: The length of path between two nodes is represented by the number of edges between them.

*/

public class DiameterOfBinaryTree {

public static class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

}

}

private int max = 0;

/**

* Main method

*

* @param args

* @throws Exception

*/

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

TreeNode root = new TreeNode(5);

root.left = new TreeNode(4);

System.out.println(new DiameterOfBinaryTree().diameterOfBinaryTree(root));

}

public int diameterOfBinaryTree(TreeNode root) {

dfs(root);

return max;

}

private int dfs(TreeNode node) {

if (node != null) {

int left = dfs(node.left);

int right = dfs(node.right);

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

return left > right ? left + 1 : right + 1;

}

return 0;

}

}