public class DiameterOfTree {
public static void main(String[] args) {
Node node = new Node(1);
node.left = new Node(2);
node.right = new Node(3);
node.left.left = new Node(4);
node.left.left.left = new Node(5);
node.left.left.left.left = new Node(6);
node.left.left.left.right = new Node(7);
node.left.left.right = new Node(8);
//System.out.println(findHeight(node));
System.out.println(diameter(node));
}
static void printInOrder(Node node) {
if(null!=node) {
printInOrder(node.left);
System.out.println(node.value);
printInOrder(node.right);
}
}
static int diameter(Node node) {
if(null==node) {
return 0;
}
int lengthLeft,lengthRight;
lengthLeft = findHeight(node.left);
lengthRight = findHeight(node.right);
int leftDiameter = diameter(node.left);
int rightDiameetr = diameter(node.right);
return Math.max(1+lengthLeft+lengthRight, Math.max(leftDiameter, rightDiameetr));
}
static int findHeight(Node node) {
if(null==node) {
return 0;
}
if(null==node.left && null==node.right) {
return 1;
}
int left ,right ;
if(null!=node.left) {
left = findHeight(node.left);
}else {
left = Integer.MIN_VALUE;
}
if(null!=node.right) {
right = findHeight(node.right);
}else {
right = Integer.MIN_VALUE;
}
return 1+ Math.max(left, right) ;
}
static class Node{
Integer value;
Node left;
Node right;
Node(Integer value){
this.value = value;
left = right = null;
}
}
}
output: 6
public static void main(String[] args) {
Node node = new Node(1);
node.left = new Node(2);
node.right = new Node(3);
node.left.left = new Node(4);
node.left.left.left = new Node(5);
node.left.left.left.left = new Node(6);
node.left.left.left.right = new Node(7);
node.left.left.right = new Node(8);
//System.out.println(findHeight(node));
System.out.println(diameter(node));
}
static void printInOrder(Node node) {
if(null!=node) {
printInOrder(node.left);
System.out.println(node.value);
printInOrder(node.right);
}
}
static int diameter(Node node) {
if(null==node) {
return 0;
}
int lengthLeft,lengthRight;
lengthLeft = findHeight(node.left);
lengthRight = findHeight(node.right);
int leftDiameter = diameter(node.left);
int rightDiameetr = diameter(node.right);
return Math.max(1+lengthLeft+lengthRight, Math.max(leftDiameter, rightDiameetr));
}
static int findHeight(Node node) {
if(null==node) {
return 0;
}
if(null==node.left && null==node.right) {
return 1;
}
int left ,right ;
if(null!=node.left) {
left = findHeight(node.left);
}else {
left = Integer.MIN_VALUE;
}
if(null!=node.right) {
right = findHeight(node.right);
}else {
right = Integer.MIN_VALUE;
}
return 1+ Math.max(left, right) ;
}
static class Node{
Integer value;
Node left;
Node right;
Node(Integer value){
this.value = value;
left = right = null;
}
}
}
output: 6
No comments:
Post a Comment