难度: Easy
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
提示：
- 树中节点数目在范围
[1, 1000]内 -100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
Submission
运行时间: 44 ms
内存: 15.1 MB
# 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:
if root is None:
return True
def dfs(p, q):
if p is None and q is None:
return True
if p is None:
return False
if q is None:
return False
return p.val == q.val and dfs(p.left, q.right) and dfs(p.right, q.left)
return dfs(root.left, root.right)
Explain
这个题解使用递归的方式来判断二叉树是否对称。主要思路是同时从左右子树开始递归遍历，比较对应位置节点的值是否相等。如果左右子树都为空，说明对称；如果只有一个子树为空，说明不对称；如果两个子树的节点值不相等，也说明不对称。在递归过程中，要将左子树的左孩子和右子树的右孩子进行比较，左子树的右孩子和右子树的左孩子进行比较。
时间复杂度: 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:
if root is None:
return True
def dfs(p, q):
# 如果左右子树都为空，说明对称
if p is None and q is None:
return True
# 如果只有一个子树为空，说明不对称
if p is None:
return False
if q is None:
return False
# 如果两个子树的节点值不相等，说明不对称
# 否则递归比较左子树的左孩子和右子树的右孩子，左子树的右孩子和右子树的左孩子
return p.val == q.val and dfs(p.left, q.right) and dfs(p.right, q.left)
# 从左右子树开始递归遍历
return dfs(root.left, root.right)
Explore
是的，这种处理方式能正确处理所有对称树的情况。当二叉树的左右子树都为空时，意味着到达了叶子节点的下一层，这是对称的基本情况。对于只有一个根节点的树，根节点的左右子树都为空，因此在根节点的递归检查中也会返回True，从而判断整棵树是对称的。
在递归解法中，检查对称性不仅涉及结构的比较，还涉及节点值的比较。递归函数首先检查当前比较的两个节点的值是否相等。如果不相等，函数会直接返回False，表明树不对称。只有当节点值相等时，才会继续递归比较其他对应的子节点。这确保了即使左右子树的结构相同，节点值不同也会被正确地识别为不对称。
迭代方法通常使用队列来模拟递归过程。首先，将根节点的左右子节点入队。然后，每次从队列中取出两个节点进行比较，并将它们的子节点按对称顺序入队：先左节点的左子节点与右节点的右子节点，然后左节点的右子节点与右节点的左子节点。如果在任何时候节点值不相等，或者一个节点为空而另一个不为空，则判断树不对称。如果队列为空，表明已经完成了所有对应节点的比较，且所有比较都表明节点对称，因此树是对称的。
可以通过调整逻辑稍微减少一些为空的检查。例如，可以将两个节点都为空的情况和其中一个节点为空的情况合并处理。具体做法是，在递归函数中，如果其中一个节点为空，就检查另一个节点是否也为空。如果两个节点都为空，返回True；如果只有一个为空，则返回False。这样可以将检查节点是否为空的次数减少到每个节点只检查一次。