给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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
进阶：
- 你可以运用递归和迭代两种方法解决这个问题吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一解
使用递归，双指针 p，q 指向树的左右节点：
1
/ \
2 p 2 q
/ \ / \
3 4 4 3
利用 p 和 q 进行递归判断：
- 终止条件：
- 越过叶节点，返回 true
- p，q 只有一个为空，返回 false
- 递推工作：
- 同时递归 p 左子树和 q 的右子树，返回值为 r1
- 同时递归 q 左子树和 p 的右子树，返回值为 r2
- 返回值：
- r1，r2 全部为 true 并且 p.val == q.val ：此时 p 和 q 是镜像对称，返回 true
- 否则：不对称，返回 false
# 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: TreeNode) -> bool:
def check(p, q):
if not p and not q: return True
if not p or not q: return False
return p.val == q.val and check(p.left, q.right) and check(p.right, q.left)
return check(root, root)
- 时间复杂度：O(n)
- 空间复杂度：O(n)
二解
利用迭代法，使用栈模拟递归调用：
# 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: TreeNode) -> bool:
stack = [root, root]
while stack:
u, v = stack.pop(), stack.pop()
if not u and not v: continue
if not u or not v or u.val != v.val: return False
stack.append(u.left)
stack.append(v.right)
stack.append(u.right)
stack.append(v.left)
return True
- 时间复杂度：O(n)
- 空间复杂度：O(n)