# 101. Symmetric Tree

### Leetcode

<https://leetcode.com/problems/symmetric-tree/>

### 題目

Given the `root` of a binary tree, *check whether it is a mirror of itself* (i.e., symmetric around its center).

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/02/19/symtree1.jpg)

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

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/02/19/symtree2.jpg)

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

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

* **方法一**

Recursion

```
var isSymmetric = function(root) {
    const isMirror = (node1, node2) => {
        if(node1 === null && node2 === null) return true;
        if(node1 === null || node2 === null) return false;
        return (node1.val === node2.val) 
            && isMirror(node1.left, node2.right)
            && isMirror(node1.right, node2.left)
    }
    
    return isMirror(root, root);
};
```

Runtime: 72 ms, faster than 90.41% of JavaScript online submissions for Symmetric Tree.

Memory Usage: 45.1 MB, less than 13.46% of JavaScript online submissions for Symmetric Tree.

* **方法二**

Iteration

```
var isSymmetric = function(root) {
    const queue = [root, root];
    
    while(queue.length) {
        const node1 = queue.shift();
        const node2 = queue.shift();
        if (node1 === null && node2 === null) continue;
        if (node1 === null || node2 === null) return false;
        if (node1.val !== node2.val) return false;
        
        // 將相對稱的 node 依序放在 queue 的最前面
        queue.push(node1.left);
        queue.push(node2.right);
        queue.push(node1.right);
        queue.push(node2.left);
    }
    return true;
};
```

Runtime: 85 ms, faster than 71.63% of JavaScript online submissions for Symmetric Tree.

Memory Usage: 44.8 MB, less than 32.01% of JavaScript online submissions for Symmetric Tree.
