日野弥生：勉強しよう
LeetCode 101 - 对称二叉树
发表于2025年02月18日
本题需要注意：轴对称要求的是根节点的左右子树轴对称，而非每个子树都满足轴对称。所以先处理根节点。然后让左右子树分别比较。递归的关键就在于比较左右子树的左结点和右节点是否等同。
递归的方式，分别对左右子树进行劈叉递归。
class Solution:
def isSymmetricIMPL(self, rootLeft: Optional[TreeNode], rootRight: Optional[TreeNode]) -> bool:
if (rootLeft is None) != (rootRight is None):
return False
if rootLeft is None and rootRight is None:
return True
if rootLeft.val != rootRight.val:
return False
return self.isSymmetricIMPL(rootLeft.right, rootRight.left) and self.isSymmetricIMPL(rootLeft.left, rootRight.right)
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
return self.isSymmetricIMPL(root.left, root.right)非递归的方式，BFS是个好的选择。可以一次性出栈两个结点，从而要求根的左右子树的后序子树劈叉进栈。
class Solution:
def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
queue = [root.left, root.right]
while queue:
left, right = queue.pop(0), queue.pop(0)
if (left is None) != (right is None):
return False
if not left and not right:
continue
if left.val != right.val:
return False
queue.append(left.left)
queue.append(right.right)
queue.append(left.right)
queue.append(right.left)
return True