|
| 1 | +class Solution { |
| 2 | + private static int treeDiameter = 0; |
| 3 | + |
| 4 | + public int diameterOfBinaryTree(TreeNode root) { |
| 5 | + calculateHeight(root); |
| 6 | + return treeDiameter-1; |
| 7 | + } |
| 8 | + |
| 9 | + private static int calculateHeight(TreeNode currentNode) { |
| 10 | + if (currentNode == null) |
| 11 | + return 0; |
| 12 | + |
| 13 | + int leftTreeHeight = calculateHeight(currentNode.left); |
| 14 | + int rightTreeHeight = 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 | + int diameter = 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 | + return Math.max(leftTreeHeight, rightTreeHeight) + 1; |
| 31 | + } |
| 32 | +} |