来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/invert-binary-tree

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

翻转一棵二叉树。

示例：

输入：

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

输出：

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

二、题解

简单题，有两种思路：递归和队列。

2.1 递归

每遍历到一个节点，调整左右子树的值。然后分别递归遍历左右子树。

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 使用队列

把根节点放到队列中，然后依次访问队列中的节点，把每个节点的左右子树位置对换，然后把左右子节点放到栈中继续遍历。

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)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

其中的一个评论给也很有意思：

如果我是你，我会把白板从下到上翻转。然后告诉他：那，这就是我翻转的二叉树。