查看原文
其他

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

脚本之家 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;
}

广度优先搜索与深度优先搜索不仅仅可以用在二叉树中,这两种遍历方法有着极其广泛的用途,当我们积攒足够多的使用案例后将会系统总结这两种遍历方法。

<END>

程序员专属T恤

商品直购链接 👇

  推荐阅读:

这是一件程序员才懂的T恤

字节终面:求最大在线峰值人数
腾讯终面:孤单的QQ号码怎么找?

京东二面:高并发设计,都有哪些技术方案?

字节一面:网站显示不出来,怎么排查?

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存