erd
BAN USEROne simple way is to print tree in level order but changing the order of printing depending on level.
int count=0;
public void printZigZag() {
int maxDepth = maxDepth(rootNode);
for (int i = 1; i <= maxDepth; i++) {
printLevelOrder(rootNode, i);
count=i;
}
}
public void printLevelOrder(Node node, int level) {
if (node == null) {
return;
}
if (level == 1) {
System.out.println(node.data);
} else {
if (count % 2 == 0) {
printLevelOrder(node.leftChild, level - 1);
printLevelOrder(node.rightChild, level - 1);
}
else
{
printLevelOrder(node.rightChild, level - 1);
printLevelOrder(node.leftChild, level - 1);
}
}
}
I guess this can be modified to to do in O(n) complexity by using queue and stack depending on the level of tree.
Its just Kadane's algo...Java implementation would go like this
- erd June 27, 2012