《剑指offer刷题笔记》26、二叉树的镜像【c++详细题解】

蔚落 2021-07-24 16:54 263阅读 0赞

### **题目** ###

输入一个二叉树，将它变换为它的镜像。

**样例**

输入树：
          8
         / \
        6  10
       / \ / \
      5  7 9 11
    
     [8,6,10,5,7,9,11,null,null,null,null,null,null,null,null] 
    输出树：
          8
         / \
        10  6
       / \ / \
      11 9 7  5
    
     [8,10,6,11,9,7,5,null,null,null,null,null,null,null,null]

### **思路** ###

**(二叉树，递归)**  O ( n ) O(n) O(n)  
仔细观察原树和镜像之后的树：

原树：  
8  
/  
6 10  
/ \\ /  
5 7 9 11

镜像后的树：  
8  
/  
10 6  
/ \\ /  
11 9 7 5  
我们可以发现镜像后的树就是将原树的所有节点的左右儿子互换！

所以我们递归遍历原树的所有节点，将每个节点的左右儿子互换即可。

**时间复杂度**  
原树仅被遍历一次，所以时间复杂度是  O ( n ) O(n) O(n)。

### **代码** ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        void mirror(TreeNode* root) { 
            if(!root) return; //递归边界
            swap(root->left,root->right); //将当前根节点的左右结点互换
            mirror(root->left); //递归左子树
            mirror(root->right);//递归右子树
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，263人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指Offer题解：java】二叉树的镜像

文章目录题目分析代码题目操作给定的二叉树，将其变换为源二叉树的镜像。二叉树的镜像定义：源二叉树

我就是我/ 2022年10月27日 05:19/ 0 赞/ 79 阅读

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

《剑指offer》刷题笔记（面试思路）：二叉树的镜像 -------------------- 转载请注明作者和出处：[http://blog.csdn.net/

亦凉/ 2022年06月09日 13:07/ 0 赞/ 68 阅读

相关《剑指offer》刷题笔记（树）：重建二叉树

《剑指offer》刷题笔记（树）：重建二叉树 -------------------- 转载请注明作者和出处：[http://blog.csdn.net/u011

左手的ㄟ右手/ 2022年06月08日 13:29/ 0 赞/ 153 阅读

相关《剑指offer》刷题笔记（树）：对称的二叉树

《剑指offer》刷题笔记（树）：对称的二叉树 -------------------- 转载请注明作者和出处：[http://blog.csdn.net/u01

以你之姓@/ 2022年06月03日 08:08/ 0 赞/ 120 阅读

相关《剑指offer刷题笔记》7、二叉树的下一个节点【c++详细题解】

题目给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。注意：如果给定的节点是中序遍历序列的最后一个，则返回空节点; 二叉树

野性酷女/ 2021年07月24日 20:17/ 0 赞/ 260 阅读

相关《剑指offer刷题笔记》25、树的子结构【c++详细题解】

题目输入两棵二叉树 A，B，判断 B 是不是 A 的子结构。我们规定空树不是任何树的子结构。样例树 A： 8

àì夳堔傛蜴生んèń/ 2021年07月24日 18:23/ 0 赞/ 295 阅读

相关《剑指offer刷题笔记》26、二叉树的镜像【c++详细题解】

题目输入一个二叉树，将它变换为它的镜像。样例输入树： 8 / \ 6 10

蔚落/ 2021年07月24日 16:54/ 0 赞/ 264 阅读

相关《剑指offer刷题笔记》6、重建二叉树【c++详细题解】

题目输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。注意：二叉树中每个节点的值都互不相同；输入的前序遍历和中序遍历一定合法；

亦凉/ 2021年07月24日 15:36/ 0 赞/ 331 阅读

相关《剑指offer刷题笔记》33、之字形打印二叉树【c++详细题解】

题目请实现一个函数按照之字形顺序从上向下打印二叉树。即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此

逃离我推掉我的手/ 2021年07月24日 14:55/ 0 赞/ 256 阅读

相关《剑指offer刷题笔记》27、对称的二叉树【c++详细题解】

题目请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。样例如下图所示二叉树[1,2,2,

水深无声/ 2021年07月24日 12:49/ 0 赞/ 269 阅读