做出这道题，说明你很有机会进入 Google

我不是女神ヾ 2022-03-17 07:48 163阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

### 题目描述 ###

翻转一棵二叉树。

**示例：**

输入：

4
       /   \
      2     7
     / \   / \
    1   3 6   9

输出：

4
       /   \
      7     2
     / \   / \
    9   6 3   1

### 解法 ###

这道题确实难度不大，可以用 **递归** 和 **非递归** 两种方法来解。

先来看递归的方法，写法非常简洁，只需要五行代码搞定：**交换当前左右节点，然后直接调用递归即可** 。

// 递归解法
    class Solution {
         
    public:
        TreeNode* invertTree(TreeNode* root) {
        
            if (!root) return NULL;
            TreeNode *tmp = root->left;
            root->left = invertTree(root->right);
            root->right = invertTree(tmp);
            return root;
        }
    };

非递归的解法跟二叉树的层序遍历一样，需要用 **queue** 来辅助。

首先把根节点排入队列中，然后从队中取出来，交换其左右节点，如果存在则分别将左右节点在排入队列中，以此类推直到队列中没有节点了再停止循环，最后返回 **root** 即可。

//  非递归解法
    class Solution {
         
    public:
        TreeNode* invertTree(TreeNode* root) {
        
            if (!root) return NULL;
            queue<TreeNode*> q;
            q.push(root);
            while (!q.empty()) {
        
                TreeNode *node = q.front(); q.pop();
                TreeNode *tmp = node->left;
                node->left = node->right;
                node->right = tmp;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            return root;
        }
    };

### 典故 ###

据说 Max Howell（ 90% google 的人都用过他写的 Homebrew ）去 Google 面试，然后 Google 要求他用白板翻转一颗二叉树，结果写不出来就被 Google 拒了。

> 事情大概是说，Max Howell 去 Google 面试，面试官说：虽然在 Google 有 90% 的工程师用你写的 Homebrew，但是你居然不能在白板上写出翻转二叉树的代码，所以滚蛋吧。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1] Max Howell

所以，如果你能做出这道题，说明你很有机会进入 Google 。

本文完。

--------------------

**今日问题：**

尝试一下在留言区，用自己熟悉的编程语言白板写出翻转二叉树的代码。

**打卡格式：**

打卡 X 天，答：xxx 。

喜欢就点击“好看”吧！