简述二叉树判断是否对称(先序遍历) ?
参考答案:
要判断一个二叉树是否对称,可以通过比较它的左右子树是否镜像对称来实现。在二叉树中,如果任意两个节点的左右子树都是镜像对称的,则这个二叉树是对称的。
使用先序遍历(根-左-右)来判断二叉树是否对称的算法大致如下:
-
递归基准情况:
- 如果两个节点都为空,则它们是对称的。
- 如果只有一个节点为空,或者两个节点的值不相等,则它们不是对称的。
-
递归情况:
- 对于两个非空节点,检查它们的左子树和右子树是否对称。这可以通过递归调用相同的函数来实现。
- 首先,检查左节点的左子树是否与右节点的右子树对称。
- 然后,检查左节点的右子树是否与右节点的左子树对称。
- 如果这两个条件都满足,那么这两个节点是对称的。
在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
函数递归地比较两个节点的左右子树,以检查它们是否镜像对称。