Accepted O(n) Java solution

  • 0

    Diameter of a tree is the maximum of:
    (a.) Diameter of left subtree
    (b.) Diameter of right subtree
    (c.) (a.) + (b.) which passes through the root
    Diameter of a tree with single node is 0 if you consider diameter as edge count and 1 if you consider diameter as node count.

    class Solution {
       public int maxDiameter = 0;
       public int diameterOfBinaryTree(TreeNode root) {
          if(root == null) return 0;
          return maxDiameter;
       public int height(TreeNode root) {
            if(root == null) return 0;
            int leftHeight = height(root.left);
            int rightHeight = height(root.right);
            maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
            return Math.max(leftHeight, rightHeight) + 1;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.