101.Symmetric Tree
===

###### tags: `Easy`,`Tree`,`DFS`,`BFS`

[101. Symmetric Tree](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).*

### 範例

**Example 1:**


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

**Example 2:**


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

**Constraints**:

* The number of nodes in the tree is in the range [1, 1000].
* -100 <= `Node.val` <= 100

**Follow up:** Could you solve it both recursively and iteratively?

### 解答
#### Python
* DFS

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def isMirror(t, r):
            if not t and not r:
                return True

            if t and r and t.val == r.val:
                return isMirror(t.left, r.right) and isMirror(t.right, r.left)

            return False

        return isMirror(root.left, root.right)

* BFS

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        q = deque([root, root])

        while q:
            t = q.popleft()
            r = q.popleft()

            if not t and not r: 
                continue
            if not t or not r or t.val != r.val: 
                return False

            q.append(t.left)
            q.append(r.right)
            q.append(t.right)
            q.append(r.left)

        return True

> [name=Ron Chen][time=Mon, Mar 13, 2023]

#### Javascript

function isSymmetric(root) {
  if (!root) return true;
  const queue = [root.left, root.right];
  while (queue.length) {
    const left = queue.shift();
    const right = queue.shift();
    if (!left && !right) continue;
    if (!left || !right) return false;
    if (left.val !== right.val) return false;

    queue.push(left.left, right.right, left.right, right.left);
  }

  return true;
}

> [name=Marsgoat][time=Mon, Mar 13, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)