跳到主要内容

简述二叉树判断是否对称(先序遍历) ?

参考答案:

要判断一个二叉树是否对称,可以通过比较它的左右子树是否镜像对称来实现。在二叉树中,如果任意两个节点的左右子树都是镜像对称的,则这个二叉树是对称的。

使用先序遍历(根-左-右)来判断二叉树是否对称的算法大致如下:

  1. 递归基准情况

    • 如果两个节点都为空,则它们是对称的。
    • 如果只有一个节点为空,或者两个节点的值不相等,则它们不是对称的。
  2. 递归情况

    • 对于两个非空节点,检查它们的左子树和右子树是否对称。这可以通过递归调用相同的函数来实现。
    • 首先,检查左节点的左子树是否与右节点的右子树对称。
    • 然后,检查左节点的右子树是否与右节点的左子树对称。
    • 如果这两个条件都满足,那么这两个节点是对称的。

在Python中,这个算法可以像这样实现:

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

def isSymmetric(root):
    return isMirror(root, root)

def isMirror(t1, t2):
    if t1 is None and t2 is None:
        return True
    if t1 is None or t2 is None:
        return False
    if t1.val != t2.val:
        return False
    return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

在这个实现中,isSymmetric函数是公开的接口,它调用isMirror函数来比较根节点的左右子树是否对称。isMirror函数递归地比较两个节点的左右子树,以检查它们是否镜像对称。