public void OptimizedMaxPath() {
OptimizedMaxPath(root);
}
private void OptimizedMaxPath(Node node) {
if (node == null) {
return;
}
Stack<Node> stack = new Stack<Node>();
int count = 0, fMax = 0, sMax = 0;
Node fNode = root, sNode = null; Node delNode = null;
while (true) {
while (node != null) {
stack.push(node);
count++;
node = node.leftChild;
}
if (stack.size() == 0) break;
node = stack.pop();
if (fMax < count) {
sMax = fMax;
fMax = count;
fNode = node;
}
if (fMax > count && count > sMax) {
sMax = count;
if(fNode.parent!=sNode)
sNode = node;
}
count--;
node=node.rightChild;
}
System.out.print("\n nodes height" + fNode.data + " : " + sNode.data + "\n");
Stack<Node> rStack = new Stack<Node>();
while(true){
if(fNode==root)break;
if(fNode.parent!=null && fNode.parent.data > sNode.data)break;
System.out.print(fNode.data+" : ");
fNode=fNode.parent;
}
while (sNode!=fNode) {
System.out.print(rStack.push(sNode) + " : ");
sNode=sNode.parent;
}
while(!rStack.isEmpty())
System.out.print(rStack.pop().data+" : ");
}
OptimizedMaxPath(root);
}
private void OptimizedMaxPath(Node node) {
if (node == null) {
return;
}
Stack<Node> stack = new Stack<Node>();
int count = 0, fMax = 0, sMax = 0;
Node fNode = root, sNode = null; Node delNode = null;
while (true) {
while (node != null) {
stack.push(node);
count++;
node = node.leftChild;
}
if (stack.size() == 0) break;
node = stack.pop();
if (fMax < count) {
sMax = fMax;
fMax = count;
fNode = node;
}
if (fMax > count && count > sMax) {
sMax = count;
if(fNode.parent!=sNode)
sNode = node;
}
count--;
node=node.rightChild;
}
System.out.print("\n nodes height" + fNode.data + " : " + sNode.data + "\n");
Stack<Node> rStack = new Stack<Node>();
while(true){
if(fNode==root)break;
if(fNode.parent!=null && fNode.parent.data > sNode.data)break;
System.out.print(fNode.data+" : ");
fNode=fNode.parent;
}
while (sNode!=fNode) {
System.out.print(rStack.push(sNode) + " : ");
sNode=sNode.parent;
}
while(!rStack.isEmpty())
System.out.print(rStack.pop().data+" : ");
}
No comments:
Post a Comment