做出这道题，说明你很有机会进入 Google
做出这道题，说明你很有机会进入 Google
五分钟学算法
发布于 2019-03-14 16:30:01
发布于 2019-03-14 16:30:01
题目描述
翻转一棵二叉树。
示例：
输入：
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，但是你居然不能在白板上写出翻转二叉树的代码，所以滚蛋吧。
Max Howell
所以，如果你能做出这道题，说明你很有机会进入 Google 。
本文完。
今日问题：
尝试一下在留言区，用自己熟悉的编程语言白板写出翻转二叉树的代码。
打卡格式：
打卡 X 天，答：xxx 。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-02-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录