锻练编程思维——每日一题：《剑指offer》二叉树的镜像

柔情只为你懂 2023-02-14 13:16 15阅读 0赞

# 题目描述 #

题目描述  
操作给定的二叉树，将其变换为源二叉树的镜像。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]  
题目给的代码框架：

# 题目分析 #

一提到二叉树，自然想到递归。  
就有了递归算法，其实还有非递归算法，一会儿说，先介绍简单的递归算法。

## 递归算法 ##

*  首先想到给了一颗二叉树（指向根结点的指针）pRoot，如果要镜像这颗二叉树，**首先应该想到要不要判断二叉树的根结点存不存在，存在你才能镜像它对吧。**
 *  二叉树的根结点不存在，return;就完事了因为void返回类型。
 *  二叉树的根结点存在，那么接下来镜像好了，什么？你觉得要判断这颗二叉树的根结点左右孩子存不存在？
 *  大可不必，因为根结点左右孩子是NULL也没关系啦，**这是概念问题，就算他们是NULL也要占一个位置的**![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 1]
 *  **直接就创临时变量去交换左右孩子结点就可以啦**，如下

TreeNode *tmp=pRoot->left;
            pRoot->left=pRoot->right;
            pRoot->right=tmp;

*  然后判断现在左孩子结点有无，有的话交换左孩子的左右孩子结点。判断右孩子结点有无，有的话交换右孩子的左右孩子结点。（**采用函数递归调用自己的形式判断+交换**）  
    这样NULL结点不也是给交换了？虽然表面看起来无伤大雅。

## 非递归算法 ##

比较抽象，暂且不论，基础时期先把递归形式的算法理解好！

# 题解代码 #

## 递归形式 ##

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
        
    public:
        void Mirror(TreeNode *pRoot) {
        
            if(!pRoot)
            {
        
                return;
            }
            TreeNode *tmp=pRoot->left;
            pRoot->left=pRoot->right;
            pRoot->right=tmp;
            if(pRoot->left)
            {
        
                Mirror(pRoot->left);
            }
            if(pRoot->right)
            {
        
                Mirror(pRoot->right);
            }
            
        }
    };

## 非递归形式 ##

我没理解这个代码，先贴在这里，感谢原题解提供者！

链接：https://www.nowcoder.com/questionTerminal/564f4c26aa584921bc75623e48ca3011?answerType=1&f=discussion
    来源：牛客网
    
    public void Mirror(TreeNode root) {
        
            if(root == null) return;
            Queue<TreeNode> nodes = new LinkedList<>();
            TreeNode curr, temp;
            nodes.offer(root);
            while(!nodes.isEmpty()){
        
                int len = nodes.size();
                for(int i = 0; i < len; i++){
        
                    curr = nodes.poll();
                    temp = curr.left;
                    curr.left = curr.right;
                    curr.right = temp;
                    if(curr.left != null) nodes.offer(curr.left);
                    if(curr.right != null) nodes.offer(curr.right);
                }
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200603084003334.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200603085552885.JPG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA==,size_16,color_FFFFFF,t_70