|
1 | 1 | classSolution { |
2 | | - |
3 | | -privatestaticinttreeDiameter =0; |
| 2 | +intresult = -1; |
4 | 3 |
|
5 | | -publicintdiameterOfBinaryTree(TreeNoderoot) { |
6 | | -calculateHeight(root); |
7 | | -intresult =treeDiameter-1; |
8 | | -treeDiameter =0; |
9 | | -returnMath.max(0,result); |
10 | | - } |
11 | | - |
12 | | -privatestaticintcalculateHeight(TreeNodecurrentNode) { |
13 | | -if (currentNode ==null) |
14 | | -return0; |
15 | | - |
16 | | -intleftTreeHeight =calculateHeight(currentNode.left); |
17 | | -intrightTreeHeight =calculateHeight(currentNode.right); |
18 | | - |
19 | | -if (leftTreeHeight !=0 ||rightTreeHeight !=0) { |
20 | | - |
21 | | -// diameter at the current node will be equal to the height of left subtree + |
22 | | -// the height of right sub-trees + '1' for the current node |
23 | | -intdiameter =leftTreeHeight +rightTreeHeight +1; |
24 | | - |
25 | | -// update the global tree diameter |
26 | | -treeDiameter =Math.max(treeDiameter,diameter); |
| 4 | +publicintdiameterOfBinaryTree(TreeNoderoot) { |
| 5 | +dfs(root); |
| 6 | +returnresult; |
27 | 7 | } |
28 | 8 |
|
29 | | -// height of the current node will be equal to the maximum of the heights of |
30 | | -// left or right subtrees plus '1' for the current node |
31 | | -returnMath.max(leftTreeHeight,rightTreeHeight) +1; |
32 | | - } |
| 9 | +privateintdfs(TreeNodecurrent) { |
| 10 | +if (current ==null) { |
| 11 | +return -1; |
| 12 | + } |
| 13 | +intleft =1 +dfs(current.left); |
| 14 | +intright =1 +dfs(current.right); |
| 15 | +result =Math.max(result, (left +right)); |
| 16 | +returnMath.max(left,right); |
| 17 | + } |
33 | 18 | } |