递归

1、两个根节点的值相等
2、左边的左子树和右边的右子树对称
3、左边的右子树和右边的左子树对称

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        return self.dfs(root.left, root.right)

    def dfs(self, p, q): # p,q分别为左子树根节点，右子树根节点
        if not p or not q: # 当两个子树都为空才对称，一个空一个不空就不对称
            return not p and not q
        return p.val == q.val and self.dfs(p.left, q.right) and self.dfs(p.right, q.left)



# 递归
# 1、两个根节点的值相等
# 2、左边的左子树和右边的右子树对称
# 3、左边的右子树和右边的左子树对称

迭代

1、左子树：左中右遍历
2、右子树：右中左遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        left = []; right = [] # 左右子树各自一个栈

        l = root.left; r = root.right
        while l or r or len(left) > 0 or len(right) > 0:
            while l and r: 
                left.append(l); l = l.left # 左子树遍历到最左节点（压入最左的一条链到栈中）
                right.append(r); r = r.right # 右子树遍历最右节点（压入最右的一条链到栈中）

            if l or r: return False # 若一个空一个非空，说明两条链节点数目不等，则肯定不对称
            l = left.pop(); r = right.pop() # 各自弹出栈顶元素
            if l.val != r.val: return False # 比较值，不等则不对称

            l = l.right; r = r.left # 左子树遍历完左中就遍历右；右子树遍历完右中就遍历左

        return True




# 迭代
# 1、左子树：左中右遍历
# 2、右子树：右中左遍历