[算法刷题笔记]二叉树练习(1)二叉树的镜像

今天药忘吃喽~ 2024-04-21 08:01 12阅读 0赞

> #### ✨ 二叉树的镜像 ####
> 
>  *  ?前言
>  *  ?二叉树的镜像
>  *   *  ??题目描述
>      *  ??思路1
>      *  ??思路2
>  *  ?总结
> 
>   
> ?个人主页: [不断前进的皮卡丘][Link 1]  
> ?博客描述: **梦想也许遥不可及，但重要的是追梦的过程，用博客记录自己的成长，记录自己一步一步向上攀登的印记**  
> ?网站推荐：千里之行，始于足下。每天坚持刷题，巩固所学知识，也为将来找工作，面试做好准备----- [刷题神器][Link 2]

## ?前言 ##

> 学习算法，还有一些知识的时候，有时候看书后以为自己懂了，结果做题就发现自己没什么思路，为此，博主决定坚持刷题，这里给大家推荐一个适合大家做题复习，准备面试的网站[点此进入][Link 2]，里面还有大量的面经，大家可以在面试之前去看看  
> ![在这里插入图片描述][15ff82da90f44be2a95cb48c93105248.png]  
> 我们可以看到里面根据不同知识层面分成对应的题库，算法也进行了对应的分类，十分的友好，接下来就开始今天的刷题之旅

## ?二叉树的镜像 ##

[二叉树的镜像][Link 3]

### ??题目描述 ###

> 描述  
> 操作给定的二叉树，将其变换为源二叉树的镜像。  
> 数据范围：二叉树的节点数 0 \\le n \\le 10000≤n≤1000 ， 二叉树每个节点的值 0\\le val \\le 10000≤val≤1000  
> 要求： 空间复杂度 O(n)O(n) 。本题也有原地操作，即空间复杂度 O(1)O(1) 的解法，时间复杂度 O(n)O(n)  
> ![在这里插入图片描述][a63c9b35f7294a7f9387e249bfa40bd4.png]  
> ![在这里插入图片描述][1a212d7935dc4521b0273eb71a9982f7.png]

### ??思路1 ###

> ?`我们可以考虑递归遍历，交换每一个节点的左右孩子节点`  
> 1️⃣如果根节点pRoot为空，返回空  
> 2️⃣交换左右子树  
> 3️⃣递归左子树  
> 4️⃣递归右子树  
> 5️⃣返回根节点  
> ![在这里插入图片描述][4b614513cd34461ca43cf08bf42a6769.jpeg]  
> ![在这里插入图片描述][097a9e46ad7246af8eb48cf43d839253.png]  
> ![在这里插入图片描述][b052178ed136480692b3e77e0a1feca4.png]

### ??思路2 ###

> ?利用栈来存放节点，然后交换左右节点  
> 1、 当 pRoot为空时，直接返回 null ；  
> 2、初始化： 栈（或队列），本文用栈stack ，并加入根节点 pRoot。  
> 3、循环交换： 当栈 stack 为空时跳出；
> 
>  *  3.1、出栈： 记为 node ；
>  *  3.2、添加子节点： 将 node 左和右子节点入栈；
>  *  3.3、交换： 交换 node 的左 / 右子节点。
> 
> 4、返回值： 返回根节点 pRoot 。  
> **图解来自牛客**  
> ![在这里插入图片描述][655efe519df5413f8e8ad07e82ea86d2.png]  
> ![在这里插入图片描述][e0ee96f1952a46abbc379950df6f9865.png]  
> ![在这里插入图片描述][762d30f7c95c4e2b93b98db8e37515ec.png]

## ?总结 ##

> 上面那两种方法是我能够想出来的思路，如果大家想要看看其他的思路的话，我们可以在牛客的题解上面看到其他人的思路 和代码，大家具体的可以去看看，也可以在上面和大家一起交流探讨  
> ![在这里插入图片描述][8219a77da7b34e928c140cec0c4cdfe2.png]  
> 相较于其他平台，他们的题单更和工作，大厂靠拢，不光有面试必刷的101到题目，还有大量大厂真题，内容也全程免费，相较于其它会员费结算的来说 非常的友好  
> ![在这里插入图片描述][f72479ebc29a42e9a728a68658f837d2.png]  
> [牛客][Link 2]还支持ACM模式，没有练习过的一定要提前适应！像某团、某为，都要求自己处理输入输出，如果不提前练习会很吃亏的！  
> 牛客的题解更新迭代也很快，讨论区也有技巧的分享，能帮你把所有盲点扫清楚，整体来说还是非常推荐去练习的~  
> 希望大家可以和博主一起坚持下去，千里之行，始于足下，让我们一起卷进大厂???

[Link 1]: https://blog.csdn.net/qq_52797170?spm=1010.2135.3001.5343
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_pkq_sf
[15ff82da90f44be2a95cb48c93105248.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/70c88837251047ecbcfcd076cd38d579.png
[Link 3]: https://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7?tpId=196&tqId=37103&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?page=1&pageSize=50&search=%25E4%25BA%258C%25E5%258F%2589%25E6%25A0%2591%25E7%259A%2584%25E9%2595%259C%25E5%2583%258F&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196&difficulty=undefined&judgeStatus=undefined&tags=583&title=%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%95%9C%E5%83%8F
[a63c9b35f7294a7f9387e249bfa40bd4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/b6bf9e97a51d44ddb27182d9d0b1308a.png
[1a212d7935dc4521b0273eb71a9982f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/62936f139c71489bbed410c123e6877a.png
[4b614513cd34461ca43cf08bf42a6769.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/39cfa42f4149458a9732721b76d05b50.jpeg
[097a9e46ad7246af8eb48cf43d839253.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/e9e36d93f0b245a1bacdc9ae45e92ced.png
[b052178ed136480692b3e77e0a1feca4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/2b289273a3a049ec8c1298e95d211f25.png
[655efe519df5413f8e8ad07e82ea86d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/c034a14981304ab88d41b62e0b14164a.png
[e0ee96f1952a46abbc379950df6f9865.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/8e6a025a35254f14bbf88a454c6238a4.png
[762d30f7c95c4e2b93b98db8e37515ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/9808b8c9b1da4352a1c50fd6d177bc80.png
[8219a77da7b34e928c140cec0c4cdfe2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/892c87b1b71e433a8c49bd03470ce104.png
[f72479ebc29a42e9a728a68658f837d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/21/8a9db2f17b59435ab0c84054b3d455e0.png