对称二叉树

1、题目

图1

2、题解

递归

终止条件：left和right不等或者left和right都为空

递归：比较\(left.left和right.right\)以及\(left.right和right.left\)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root: return True

        def dfs(left,right):
            if not(left or right):
                return True
            
            if not (left and right):
                return False
            
            if left.val != right.val:
                return False

            return dfs(left.left,right.right) and dfs(left.right,right.left)
        
        return dfs(root.left,root.right)

迭代

实现思路与递归一样：将比较的两个节点放入队列中，比较完毕后弹出队列

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root or not (root.left or root.right): return True

        que = [root.left, root.right]

        while que:
            left = que.pop(0)
            right = que.pop(0)

            if not (left or right):
                continue
            if not (left and right):
                return False
            if left.val != right.val:
                return False
            
            que.append(left.left)
            que.append(right.right)

            que.append(left.right)
            que.append(right.left)
        
        return True