解析LeetCode第226号题目：反转二叉树
今天给大家讲解一道微软一面的算法题，也是leetcode第226号题目，反转二叉树，就像这样：
简单讲就是把每个节点的左子树和右子树进行交换 。
显然，这需要我们能够遍历该二叉树。
那么遍历二叉树就有两种经典的解法：深度优先遍历，deep first search，简称dfs；另一个是广度优先遍历，breadth first search，简称bfs。
深度优先搜索顾名思义，深度优先搜索是我总是优先访问“ 节点的子节点的子节点 。。”，这是什么意思呢？对于给定的二叉树，我们首先访问节点4：
接下来访问4的左子树2：
再接下来依然访问2的左子树1：
1是叶子节点，其左右子树都为空，因此返回上一个节点2，然后访问其右子树3，重复上述过程直到所有节点访问完毕。
你会发现，这其实是一个递归过程：
深度优先搜索非常适合用递归代码编写。
回到这个题目，代码就可以这样写：
treenode* inverttree(treenode* root) { // 如果是空节点，直接访问 if (root == nullptr) return nullptr; // 找到当前节点的左右字节点，并交换 auto* left = root->left; auto* right = root->right; root->left = right; root->right = left; // 处理当前节点的左右子节点 inverttree(left); inverttree(right); return root;}接下来我们看广度优先搜索。
广度优先搜索个人认为广度优先搜索相对来说更容易理解，通俗的讲，广度优先搜索是“ 先把同辈访问完再访问下一辈 ”，因此这一种“ 层级 ”遍历方法，先是访问第一层，然后是第二层。。直到最后一层，就像这样：
在这里我们可以使用一个队列，先把根节点4放入队列中，然后从队列依次取出节点，交换其左右字数，并将该节点的左右字数也放到队列中，重复上述过程直到队列为空，用代码就是这样实现：
treenode* inverttree(treenode* root) { if (root == nullptr) return nullptr; // 定义队列，并把根节点放到队列中 queue q; q.push(root); while(!q.empty()) { // 从队列中取出节点 auto* t = q.front(); q.pop(); // 交换该节点的左右子树 auto* left = t->left; auto* right = t->right; t->left = right; t->right = left; // 如果该节点的左右子树不空则放到队列 if (left) q.push(left); if (right) q.push(right); } return root;}广度优先搜索与深度优先搜索不仅仅可以用在二叉树中，这两种遍历方法有着极其广泛的用途，当我们积攒足够多的使用案例后将会系统总结这两种遍历方法。
科普系列：低速容错CAN的容错机制介绍
iPhone8最新消息：苹果真抠 内存3GB能干点啥？小米6笑了
海量数据分析应用：用大数据技术实现流感的预警
机器视觉系统—光源篇（一）
初学C语言 先搞懂这些基础知识再谈深度学习吧！
解析LeetCode第226号题目：反转二叉树
发动机螺栓拧紧工艺及力矩检验
SiC功率器件在 PCIM Europe 全面展示
避障技术再提升，扫地机器人避障不止于精准
聚焦传感器产业，四川这两个大项目亮相
358芯片引脚功能及参数
《狼与香辛料》的作者做了一部VR动漫!居然还支持中文
AI安防落地过程中 安企要十八般武艺样样俱全
BK7238,上海博通-单芯片Wi-Fi802.11n、低功耗蓝牙BLE5.2组合解决方案
!HP66332A/HP66332A/HP66332A电源
浮标式自动在线监测系统的特点及注意事项的介绍
魅族PRO7曝光： 双曲面屏加持， 8G运存惊艳了！
晶盛机电成功发布6英寸双片式SiC碳化硅外延设备
基于S3C2410嵌入式设备的U-Boot移植流程教程
西门子牵手微软对阵通用电气 物联网之争再升温
简单讲就是把每个节点的左子树和右子树进行交换 。
显然，这需要我们能够遍历该二叉树。
那么遍历二叉树就有两种经典的解法：深度优先遍历，deep first search，简称dfs；另一个是广度优先遍历，breadth first search，简称bfs。
深度优先搜索顾名思义，深度优先搜索是我总是优先访问“ 节点的子节点的子节点 。。”，这是什么意思呢？对于给定的二叉树，我们首先访问节点4：
接下来访问4的左子树2：
再接下来依然访问2的左子树1：
1是叶子节点，其左右子树都为空，因此返回上一个节点2，然后访问其右子树3，重复上述过程直到所有节点访问完毕。
你会发现，这其实是一个递归过程：
深度优先搜索非常适合用递归代码编写。
回到这个题目，代码就可以这样写：
treenode* inverttree(treenode* root) { // 如果是空节点，直接访问 if (root == nullptr) return nullptr; // 找到当前节点的左右字节点，并交换 auto* left = root->left; auto* right = root->right; root->left = right; root->right = left; // 处理当前节点的左右子节点 inverttree(left); inverttree(right); return root;}接下来我们看广度优先搜索。
广度优先搜索个人认为广度优先搜索相对来说更容易理解，通俗的讲，广度优先搜索是“ 先把同辈访问完再访问下一辈 ”，因此这一种“ 层级 ”遍历方法，先是访问第一层，然后是第二层。。直到最后一层，就像这样：
在这里我们可以使用一个队列，先把根节点4放入队列中，然后从队列依次取出节点，交换其左右字数，并将该节点的左右字数也放到队列中，重复上述过程直到队列为空，用代码就是这样实现：
treenode* inverttree(treenode* root) { if (root == nullptr) return nullptr; // 定义队列，并把根节点放到队列中 queue q; q.push(root); while(!q.empty()) { // 从队列中取出节点 auto* t = q.front(); q.pop(); // 交换该节点的左右子树 auto* left = t->left; auto* right = t->right; t->left = right; t->right = left; // 如果该节点的左右子树不空则放到队列 if (left) q.push(left); if (right) q.push(right); } return root;}广度优先搜索与深度优先搜索不仅仅可以用在二叉树中，这两种遍历方法有着极其广泛的用途，当我们积攒足够多的使用案例后将会系统总结这两种遍历方法。
科普系列：低速容错CAN的容错机制介绍
iPhone8最新消息：苹果真抠 内存3GB能干点啥？小米6笑了
海量数据分析应用：用大数据技术实现流感的预警
机器视觉系统—光源篇（一）
初学C语言 先搞懂这些基础知识再谈深度学习吧！
解析LeetCode第226号题目：反转二叉树
发动机螺栓拧紧工艺及力矩检验
SiC功率器件在 PCIM Europe 全面展示
避障技术再提升，扫地机器人避障不止于精准
聚焦传感器产业，四川这两个大项目亮相
358芯片引脚功能及参数
《狼与香辛料》的作者做了一部VR动漫!居然还支持中文
AI安防落地过程中 安企要十八般武艺样样俱全
BK7238,上海博通-单芯片Wi-Fi802.11n、低功耗蓝牙BLE5.2组合解决方案
!HP66332A/HP66332A/HP66332A电源
浮标式自动在线监测系统的特点及注意事项的介绍
魅族PRO7曝光： 双曲面屏加持， 8G运存惊艳了！
晶盛机电成功发布6英寸双片式SiC碳化硅外延设备
基于S3C2410嵌入式设备的U-Boot移植流程教程
西门子牵手微软对阵通用电气 物联网之争再升温