> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/tree/101-symmetric-tree.md).

# 101 Symmetric Tree

## 101. Symmetric Tree

## 1. Question

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree`[1,2,2,3,4,4,3]`is symmetric:

```
    1
   / \
  2   2
 / \ / \
3  4 4  3
```

But the following`[1,2,2,null,3,null,3]`is not:

```
    1
   / \
  2   2
   \   \
   3    3
```

**Note:**\
Bonus points if you could solve it both recursively and iteratively.

## 2. Implementation

**(1) DFS recursion**

```java
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isSymmetric(root, root);
    }

    public boolean isSymmetric(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) return true;
        if (node1 == null || node2 == null) return false;
        return node1.val == node2.val && isSymmetric(node1.left, node2.right) && isSymmetric(node1.right, node2.left);
    }
}
```

**(2) BFS iteration**

```java
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode node1 = queue.remove();
            TreeNode node2 = queue.remove();

            if (node1 == null && node2 == null) {
                continue;
            }
            else if (node1 == null || node2 == null || node1.val != node2.val) {
                return false;
            }

            queue.add(node1.left);
            queue.add(node2.right);
            queue.add(node1.right);
            queue.add(node2.left);
        }
        return true;
    }
}
```

## 3. Time & Space Complexity

DFS recursion: 时间复杂度: O(n), 空间复杂度: O(n)

BFS iteration: 时间复杂度: O(n), 空间复杂度: O(n)