来源：力扣 （LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、题目描述
翻转一棵二叉树。
示例：
输入：
|
1 2 3 4 5 |
4 / \ 2 7 / \ / \ 1 3 6 9 |
输出：
|
1 2 3 4 5 |
4 / \ 7 2 / \ / \ 9 6 3 1 |
二、题解
简单题，有两种思路：递归和队列。
2.1 递归
每遍历到一个节点，调整左右子树的值。然后分别递归遍历左右子树。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
TreeNode *invertTree(TreeNode *root) { TreeNode *p; if (root == nullptr) { return nullptr; } // 调整左右子树 p = root->left; root->left = root->right; root->right = p; // 遍历左右子树 invertTree(root->left); invertTree(root->right); return root; } |
2.2 使用队列
把根节点放到队列中，然后依次访问队列中的节点，把每个节点的左右子树位置对换，然后把左右子节点放到栈中继续遍历。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
TreeNode *invertTree(TreeNode *root) { queue<TreeNode *> q; TreeNode *node, *tmp; if (root == nullptr) { return nullptr; } // 根节点入队 q.push(root); while (!q.empty()) { // 取队首元素 node = q.front(); q.pop(); // 调换左右子树 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％的工程师使用您编写的软件 (Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
其中的一个评论给也很有意思：
如果我是你，我会把白板从下到上翻转。然后告诉他：那，这就是我翻转的二叉树。
