微软一面算法题：反转二叉树

脚本之家 2022-09-29

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;
}