# LeetCode226. Invert Binary Tree（二叉树 / 模拟）

## LeetCode226. Invert Binary Tree（二叉树 / 模拟）

• Easy
• Accepted：301,365
• Submissions：527,985

Invert a binary tree.

Example:

Input:

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

Output:

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

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f* off.

### 链接

https://leetcode.com/problems/invert-binary-tree

### 代码

• Runtime: 4 ms, faster than 100.00% of C++ online submissions for Invert Binary Tree.
• Memory Usage: 9.2 MB, less than 40.49% of C++ online submissions for Invert Binary Tree.
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL)
return NULL;
invertTree(root->left);
invertTree(root->right);
swap(root->left, root->right);
return root;
}
};
• Runtime: 4 ms, faster than 100.00% of C++ online submissions for Invert Binary Tree.
• Memory Usage: 9.2 MB, less than 30.37% of C++ online submissions for Invert Binary Tree.
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL)
return NULL;
queue <TreeNode*> q;
q.push(root);
while (!q.empty())
{
int n = q.size();
for (int i = 0 ; i < n; ++i)
{
TreeNode*p = q.front();
q.pop();
if (p)
swap(p->left, p->right);
if (p->left != NULL)
q.push(p->left);
if (p->right != NULL)
q.push(p->right);
}
}
return root;
}
};

The end.
2019年3月7日 星期四