《剑指offer》刷题笔记（面试思路）：二叉树的镜像

亦凉 2022-06-09 13:07 83阅读 0赞

# 《剑指offer》刷题笔记（面试思路）：二叉树的镜像 #

--------------------

*  **转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net_u011475210]**
 *  **代码地址：[https://github.com/WordZzzz/Note/tree/master/AtOffer][https_github.com_WordZzzz_Note_tree_master_AtOffer]**
 *  **刷题平台：[https://www.nowcoder.com/][https_www.nowcoder.com]**
 *  **题  库：剑指offer**
 *  **编  者：WordZzzz**

--------------------

*  剑指offer刷题笔记面试思路二叉树的镜像
    
     *  题目描述
     *  解题思路
     *  C版代码实现
        
         *  递归
         *  层序遍历
     *  Python版代码实现
        
         *  递归
         *  层序遍历

## 题目描述 ##

操作给定的二叉树，将其变换为源二叉树的镜像。

二叉树的镜像定义：

源二叉树 
                8
               /  \
              6   10
             / \  / \
            5  7 9 11
    镜像二叉树
                8
               /  \
              10   6
             / \  / \
            11 9 7  5

## 解题思路 ##

还是BFS和DFS的套路，要么递归实现要么利用队列进行层序遍历。

## C++版代码实现 ##

### 递归 ###

### 层序遍历 ###

/*
    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* node;
            queue<TreeNode*> que;
            que.push(pRoot);
            while(!que.empty()){
                node = que.front();
                que.pop();
                swap(node->left, node->right);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
    };

## Python版代码实现 ##

### 递归 ###

### 层序遍历 ###

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # 返回镜像树的根节点
        def Mirror(self, root):
            # write code here
            if not root: return
            a=[root]
            while a:
                b=[]
                for node in a:
                    node.left,node.right = node.right,node.left
                    if node.left:
                        b.append(node.left)
                    if node.right:
                        b.append(node.right)
                a=b

**系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～**

**完的汪(∪｡∪)｡｡｡zzz**

[http_blog.csdn.net_u011475210]: http://blog.csdn.net/u011475210
[https_github.com_WordZzzz_Note_tree_master_AtOffer]: https://github.com/WordZzzz/Note/tree/master/AtOffer
[https_www.nowcoder.com]: https://www.nowcoder.com/