非递归写法

好像没见到详细的非递归,正好看了别人的代码有点启发,就自己写下来了

首先看一下镜像过程:

思路:
当处理新的一层时,依次(从左至右)取得每个结点,并交换他们的左右子结点,因为是从第一层开始往下的,所以只需要在每次处理一层时依次把每一个结点的左右子结点交换一下,就会在处理完整棵树时,所有结点都交换了一遍

代码:

class Solution {
public:
    void Mirror(TreeNode *pRoot) 
    {
        //传入头结点为空直接返回
        if(!pRoot) return ;
        queue<TreeNode *> que;
        //在while操作之前把头结点加入队列,否则队列为空直接结束
        que.push(pRoot);

        while(!que.empty())
        {
            //获取每一层的结点数,即会对这一层的queSize个结点都执行交换操作
            int queSize = que.size();
            //处理完一个结点后,计数-1
            while(queSize--)
            {
                //取得当前队列第一个元素(并非出队)
                TreeNode *temp = que.front();
                //出队
                que.pop();

                //先交换,再把其左右结点入队
                //定义临时的TreeNode类型指针,用于交换左右结点
                TreeNode *swap;
                swap = temp->left;
                temp->left = temp->right;
                temp->right = swap;

                //如果左(或右)结点不为空,就加入队列
                if(temp->left) {que.push(temp->left);}
                if(temp->right) {que.push(temp->right);}
            }//继续对这一层的下一个结点进行操作
        }//队列不空时,获取下一层结点的个数,并会执行相应次数的交换与入队操作
    }
};