6-2 二叉树转双链表 (20 分)
（微软面试题）将二叉树转换为双向链表，直接使用二叉树节点作为双向链表的节点，只需改变各节点中left和right指针的值，使其分别指向链表中的左边（前序）节点和右边（后继）节点。转换后，从双向链表最左 (右) 端的节点出发，沿right (left) 指针遍历出的值序列与二叉树中序遍历 (的反转) 结果必须一致。
函数接口定义：
template <typename E> BinNode<E>* transformBinTreeToDLList(BinNode<E>* root); 将二叉树转换为双向链表，返回链表最左端节点的位置。 开始时，指针root指向二叉树的根节点。
裁判测试程序样例：
#include <iostream>
template <typename E> class BinNode{
public:
virtual ~BinNode() {}
virtual BinNode* left() const = 0; //返回left指针值
virtual BinNode* right() const = 0; //返回right指针值
virtual void setLeft(BinNode* ) = 0; //设置left指针
virtual void setRight(BinNode* ) = 0; //设置right指针
virtual bool isLeaf() = 0; }; //二叉树节点
template <typename E> BinNode<E>* constructBinTree(const int N); //构建二叉树，生成中序遍历序列，返回根节点位置（过程省略）
template <typename E> BinNode<E>* transformBinTreeToDLList(BinNode<E>* root);
int main() {
int N; //二叉树节点数量
... BinNode<int>* root = constructBinTree<int>(N);
root = transformBinTreeToDLList<int>(root); ... 遍历双向链表，并与二叉树中序遍历序列比较，如果匹配成功， 输出"correct", 否则输出"wrong"。（过程省略） ... return 0;
}
/* 请在这里填写答案 */
输入样例：
第一行给出正整数N (1≤N≤10000), 表示二叉树节点数量。 第二行给出N个整数，二叉树各节点的整数值。
7
9 7 5 19 11 13 21
输出样例：
输出双向链表是否正确。
correct
样例的二叉树及转换后的双向链表
题解
#include<stack>
template <typename E>
BinNode<E>* transformBinTreeToDLList(BinNode<E>* root){
stack<BinNode<E>*> restore;
stack<BinNode<E>*> tempt;
BinNode<E>* new_root;
while(root->left()!=NULL){
restore.push(root);
root=root->left();
}
new_root=root;
while(root!=NULL||!restore.empty()){
while(root!=NULL){
restore.push(root);
root=root->left();
}
if(!restore.empty()){
root=restore.top();
tempt.push(root);
restore.pop();
root=root->right();
}
}
while(!tempt.empty()){
root=tempt.top();
tempt.pop();
BinNode<E>* flag;
if(!tempt.empty())
flag=tempt.top();
else{
break;
}
root->setLeft(flag);
flag->setRight(root);
}
return new_root;
}