数据结构Day5--二叉树的镜像

数据结构Day5--二叉树的镜像

剑指 Offer 27. 二叉树的镜像

看完之后题目之后我愿称之为:左右子树互换问题.
镜像即左右子树互换顺序。

1.递归：
分冶法：大问题拆分成小问题。
交换整棵树=①交换根左孩子的左右子树。
②交换根的右孩子的左右子树
③最后根的左右孩子交换一下。

递归出口:树空。即遍历到树的叶子节点 则回溯。

void Switch(BiTree T){
	if(T){
		Switch(T->lchild);
		Switch(T->rchild);
		tmp=T->lchild;
		T->lchild=T->rchild;
		T->rchild=tmp;
	}
}	

2.层次遍历…感慨一下最近刷王道发现很多层次遍历的题都可以用递归来实现。

1.每访问一个节点(对头元素出队)，首先判断一下只要该节点的左右孩子有一个不空 就将该节点的左右孩子交换顺序。
2.然后再将交换后的左右节点入队。
重复1.2 直到队空

二、回顾层次遍历的过程:
①根节点入队

---

②队头出队，访问之。
③左子树不空入队。右子树不空 入队。

void Switch(BiTree &T){
    InitQueue(Q);
    BiTree p=T;
    //队头入队
    EnQueue(Q,p);
    while(!IsEmpty(Q)){
        DeQueue(Q,p);
        if(p->lchild || p->rchild){
            temp=p->lchild;
            p->lchild=p->rchild;
            p->rchild=temp;
        }
        if(p->lchild){
            EnQueue(Q,p->lchild);
        }
        if(p->rchild){
            EnQueue(Q,p->rchild);
        }
    }