Santhosh Kumar
BAN USERpublic static Node PairWiseSwap(Node root) {
if (root == null || root.next == null)
{
return root;
}
Node a = root;
Node b = root.next;
root = b; // after swap b will be the head of the list
do {
a.next = b.next;
b.next = a;
b.prev = a.prev;
a.prev = b;
// Example in list a,b,c,d after swapping nodes 'a' & 'b' pointers , 'c.prev' should be made point to 'a' now .. The list will be b,a,c,d now . After swapping 'c' & 'd' , a.next should be set to d . Now the list is b,a,d,c
if (a.next != null)
{
a.next.prev = a;
}
if(b.prev != null)
{
b.prev.next = b;
}
a = a.next;
b = (a != null)? a.next : null;
} while ( a != null && b != null)
return root;
}
The solution here will return the level order traversal in zigzag manner .
Idea: Use two stacks and a flag for identifying whether the traversal direction of the current level is a left-to-right or right-to-left.
If current level is left to right , push the left and right sub trees in stack s2 or else right and left sub tree if right-to-left traversal. (when you pop the stack , nodes will be in reverse order)
If s1 is empty, swap s1 and s2 now the next level will be copied to s1. And also toggle the traversal direction flag.
Example tree :
3
/ \
9 20
/ \ / \
4 6 15 7
Output:
[
[3],
[20,9],
[4,6,15,7]
]
code
- Santhosh Kumar May 23, 2013