剑指 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); } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)