Friday, March 27, 2015

Diameter of a tree

My last post pumped me to calculate the diameter of a tree. And there is actually the question: 


The diameter of a tree is the number of nodes on the longest path between two leaves in the tree. The diagram below shows a tree with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).
In particular, note that the diameter of a tree T is the largest of the following quantities:
the diameter of T's left subtree
the diameter of T's right subtree
the longest path between leaves that goes through the root of T
Given the root node of the tree, return the diameter of the tree


public static int maxDepth(TreeNode root){
  if(root == null)
   return 0;
  if(root.left == null && root.right == null)
   return 1;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
 }
 public static int Diameter(TreeNode root){
  if(root == null)
   return 0;
  if(root.left == null && root.right == null)
   return 1;
  return Math.max(Math.max(Diameter(root.left), Diameter(root.right)), maxDepth(root.left) + maxDepth(root.right));
 }

No comments:

Post a Comment