Google : Convert a binary tree into a double linked spiral list

//Write a program to convert binary tree in to doubly linked list such that
//doubly linked list represents the spiral order of given tree using recursion,
//Inplace(no Extra Space except recursion memory stack)
//
//given pointer to head of binary tree
//
// 1
/// \
//2   3
/// \ / \
//4 5 6 7
//         /    \
//        8            9
//
//doubly linked list represent
//
//head-> 1 2 3 7 6 5 4

求助啊，这题我话了六个小时才编出来的，用了很搓的办法，哪位大神给个neat点的解决方案！！！！！！！！！！

好的，说一下我的解答：
可以使用递归把二叉树转换为如下结构
1
/
2 - 3
/     
4- 5 - 6 -7
/   
8 - 9

类似于一个广义表，然后再转换为所需的结构

第一步转换可以参照版内的那个递归O(1)空间复杂度链接sibling节点的那题

第一次做面试题～
用一个队列和一个栈做了一下非递归的...
不符合题目要求，不过还是要纪念一下@@