微软面试100题(15)：非递归生成一个棵树的镜像

这道题的含义就是复制一颗给定的树，把每个结点的左子树变成右子树。

第15题：
题目：输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。   
例如输入：
  8
  / \
  6 10
 /\ /\
5 7 9 11

输出：
  8
  / \
 10 6
 /\ /\
11 9 7 5

其递归算法很简单，在上一篇文章中有写。

非递归算法：

类似与先序遍历树的非递归算法，其核心在于，对于每个节点，先遍历左边。如果没有左子树或遍历完左子树，无需入栈/从栈中移除当前节点

如果一个点具有左子树，那么入栈，记录此节点，因为从它的左树回来的时候，要继续遍历他的右节点。

如果没有左子树，那么显然，直接遍历右边即可，回到这个节点的时候不用任何操作，只需继续回到他的父亲就可以了。所以，当处理右节点时，不需要入栈，并且在读右子树的时候，把这个节点直接出栈。

每次读到一个新节点时（1.读取一个左节点，2读取一个右结点），复制当前节点，并建立其与父节点的正确关系。

代码中用了两个指向节点的指针的数组来当作栈，并用一个指针保存地一个复制后的树的根节点。

Node* MirrorTreeNR(Node* head){

    if(!head) return NULL;

    Node *srcstack[1000], *deststack[1000];
    Node **srclist = srcstack;
    Node **destlist = deststack;

    Node *dhead = NULL;
    Node *sroot, *droot;
    sroot = droot = NULL;
    //copy the head node
    sroot= head;
    char isRight = 0;
    while(sroot!=NULL || (*srclist) !=NULL){
        while(sroot){
            srclist ++;
            *srclist = sroot;
            //copy sroot
            Node *tmp = (Node *)malloc(sizeof(Node));
            tmp->value = sroot->value;
            if(dhead == NULL) dhead = tmp;
            if(droot !=NULL){
                if(isRight == 1){
                    droot->left = tmp;
                }
                else{
                    droot->right = tmp;
                }
            }
            isRight = 0;
            droot = tmp;
            destlist ++;
            *destlist = droot;

            sroot = sroot->left;
        }
        if(*srclist!=NULL){
            sroot = *srclist;
            droot = *destlist;
            sroot = sroot->right;
            isRight = 1;
            *srclist = NULL;
            srclist --;
            *destlist = NULL;
            destlist --;
        }
    }
    return dhead;
}