58 对称的二叉树

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。

示例：

对称:
    8
   / \
  6   6
 / \ / \
5  7 7  5

不对称:
    8
   / \
  6   6
 / \ / \
5  7 7  9

解题思路

核心思想：递归比较左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点。

Python 实现

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def is_symmetrical(root):
    """
    判断二叉树是否对称

    Args:
        root: 二叉树根节点

    Returns:
        bool: 是否对称
    """
    if not root:
        return True

    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False

        return (left.val == right.val and
                is_mirror(left.left, right.right) and
                is_mirror(left.right, right.left))

    return is_mirror(root.left, root.right)


# 测试代码
if __name__ == "__main__":
    # 对称的树
    root1 = TreeNode(8)
    root1.left = TreeNode(6)
    root1.right = TreeNode(6)
    root1.left.left = TreeNode(5)
    root1.left.right = TreeNode(7)
    root1.right.left = TreeNode(7)
    root1.right.right = TreeNode(5)

    # 不对称的树
    root2 = TreeNode(8)
    root2.left = TreeNode(6)
    root2.right = TreeNode(6)
    root2.left.left = TreeNode(5)
    root2.left.right = TreeNode(7)
    root2.right.left = TreeNode(7)
    root2.right.right = TreeNode(9)

    print(f"树1对称: {is_symmetrical(root1)}")
    print(f"树2对称: {is_symmetrical(root2)}")

# 输出:
# 树1对称: True
# 树2对称: False