微软一面算法题：反转二叉树
The following article is from 小风算法 Author 陆小风
来源：小风算法（ID: gh_0b614ff6f4cc）
已获得原公众号的授权转载
大家好，我是小风哥，首先祝大家端午节假期快乐~
今天给大家讲解一道微软一面的算法题，也是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<TreeNode*> 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;
}
广度优先搜索与深度优先搜索不仅仅可以用在二叉树中，这两种遍历方法有着极其广泛的用途，当我们积攒足够多的使用案例后将会系统总结这两种遍历方法。
<END>
程序员专属T恤
推荐阅读：