LeetCode题目（Python实现）：对称二叉树

浅浅的花香味﹌ 2023-07-15 02:47 1阅读 0赞

### 文章目录 ###

*  题目
 *   *  想法一：递归
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  想法二：迭代
     *   *  算法实现
         *  执行结果
     *  小结

# 题目 #

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 `[1,2,2,3,4,4,3]` 是对称的。

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

但是下面这个 \[1,2,2,null,3,null,3\] 则不是镜像对称的:

1
       / \
      2   2
       \   \
       3    3

## 想法一：递归 ##

### 算法实现 ###

def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        return self.isSymmetric(root.left, root.right)
    
    def isSymmetric(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if type(p) != type(q):
            return False
        if p.val != q.val:
            return False
        return self.isSymmetric(p.left, q.right) and self.isSymmetric(p.right, q.left)

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 36 ms, 在所有 Python3 提交中击败了78.63%的用户  
**内存消耗** : 13.5 MB, 在所有 Python3 提交中击败了5.05%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

## 想法二：迭代 ##

### 算法实现 ###

from collections import deque
    def isSymmetric(self, root: TreeNode) -> bool:
        def check(p, q):
            if not p and not q:
                return True
            if type(p) != type(q):
                return False
            if p.val != q.val:
                return False
            return True
    
        if not root:
            return True
    
        deq = deque([(root.left, root.right), ])
        while deq:
            p, q = deq.popleft()
            if not check(p, q):
                return False
    
            if p:
                deq.append((p.left, q.right))
                deq.append((p.right, q.left))
    
        return True

### 执行结果 ###

![在这里插入图片描述][20200315005754525.png]

## 小结 ##

和上一道题十分相似，所以运用两种方法即可解出。在之前的代码上稍加修改即可，其实我首先想到的是迭代，反而递归考虑了很久才想出来。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: /images/20230529/e21ee299716d464b9dad6c4e5776074f.png
[20200315005754525.png]: /images/20230529/a2ac5ba764564a76b075995e79b7c2ee.png