# 101. Symmetric Tree

{% embed url="<https://leetcode.com/problems/symmetric-tree/>" %}

`Tree`特定层内部的比较，肯定先想到`level order traversal`，那就直接`BFS`。

但既然在练习`DFS`，就把`DFS`也写一下吧...这边不太一样的是每次加进`stack`的不是单个`node`，而是当前`node pair`分别的左右配对，这样就可以一直比较左右对称位置的`node val`。

{% tabs %}
{% tab title="BFS" %}

```python
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        q = collections.deque([root])
        while q:
            n = len(q)
            level = []
            for _ in range(n):
                node = q.popleft()
                if node:
                    level.append(node.val)
                    q.append(node.left if node.left else None)
                    q.append(node.right if node.right else None)
                else:
                    level.append(None)
            for i in range(len(level)//2):
                if level[i] != level[-1-i]: return False
        return True
```

{% endtab %}

{% tab title="DFS" %}

```python
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        stack = collections.deque([(root.left, root.right)])
        while stack:
            l, r = stack.pop()
            if not l and not r: continue
            if not l or not r or l.val != r.val: return False
            stack.append((l.left, r.right))
            stack.append((l.right, r.left))
        return True
```

{% endtab %}

{% tab title="DFS Recursive" %}

```python
class Solution:
    def dfs(self, l, r):
        if l and r:
            # 当前配对相等，外子配对相等，内子配对相等
            return all((l.val == r.val, self.dfs(l.left, r.right), self.dfs(l.right, r.left)))
        elif not l and not r: return True
        elif not l or not r: return False
        
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        return self.dfs(root.left, root.right)
```

{% endtab %}
{% endtabs %}
