101. 对称二叉树

题目

给你一个二叉树的根节点 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

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

解答

思路

两棵对称的树：

• 根节点相同
• 左子树和右子树对称
• 右子树和左子树对称

代码

Python 代码

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is q

        return p.val == q.val \
            and self.isSameTree(p.left, q.right) \
            and self.isSameTree(p.right, q.left)
    
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.isSameTree(root.left, root.right)

这里利用的上一题的代码，其中 isSameTree(p, q) 的含义是 p, q 是否对称。因此只需要 root.left, root.right 对称即可。

TODO：迭代算法