# 226. Invert Binary Tree

### Leetcode

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

### 題目

Given the `root` of a binary tree, invert the tree, and return *its root*.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/03/14/invert1-tree.jpg)

```
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/03/14/invert2-tree.jpg)

```
Input: root = [2,1,3]
Output: [2,3,1]
```

**Example 3:**

```
Input: root = []
Output: []
```

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

Recursion

```
var invertTree = function(root) {
    if (root === null) return null;
    invertTree(root.left);
    invertTree(root.right);
    [root.left, root.right] = [root.right, root.left];
    return root;
};
```

Runtime: 81 ms, faster than 58.32% of JavaScript online submissions for Invert Binary Tree.

Memory Usage: 42.3 MB, less than 54.64% of JavaScript online submissions for Invert Binary Tree.

* **方法二**

Iteration

```
var invertTree = function(root) {
    if(root === null) return null;
    
    const queue = [root];
    while (queue.length) {
        const node = queue.shift();
        [node.left, node.right] = [node.right, node.left];
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
    }
    return root;
};
```

Runtime: 116 ms, faster than 14.73% of JavaScript online submissions for Invert Binary Tree.

Memory Usage: 42.6 MB, less than 18.98% of JavaScript online submissions for Invert Binary Tree.
