|
| 1 | +classSolution { |
| 2 | +privatestaticinttreeDiameter =0; |
| 3 | + |
| 4 | +publicintdiameterOfBinaryTree(TreeNoderoot) { |
| 5 | +calculateHeight(root); |
| 6 | +returntreeDiameter-1; |
| 7 | + } |
| 8 | + |
| 9 | +privatestaticintcalculateHeight(TreeNodecurrentNode) { |
| 10 | +if (currentNode ==null) |
| 11 | +return0; |
| 12 | + |
| 13 | +intleftTreeHeight =calculateHeight(currentNode.left); |
| 14 | +intrightTreeHeight =calculateHeight(currentNode.right); |
| 15 | + |
| 16 | +// if the current node doesn't have a left or right subtree, we can't have |
| 17 | +// a path passing through it, since we need a leaf node on each side |
| 18 | +if (leftTreeHeight !=0 &&rightTreeHeight !=0) { |
| 19 | + |
| 20 | +// diameter at the current node will be equal to the height of left subtree + |
| 21 | +// the height of right sub-trees + '1' for the current node |
| 22 | +intdiameter =leftTreeHeight +rightTreeHeight +1; |
| 23 | + |
| 24 | +// update the global tree diameter |
| 25 | +treeDiameter =Math.max(treeDiameter,diameter); |
| 26 | + } |
| 27 | + |
| 28 | +// height of the current node will be equal to the maximum of the heights of |
| 29 | +// left or right subtrees plus '1' for the current node |
| 30 | +returnMath.max(leftTreeHeight,rightTreeHeight) +1; |
| 31 | + } |
| 32 | +} |