力扣题目101:对称二叉树

作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化：企业实战案例
python源码解读
程序员必备的数学知识与应用
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级

题目描述

给定一个二叉树，检查它是否是镜像对称的。

输入格式

• root：二叉树的根节点。

输出格式

• 返回布尔值，表示树是否对称。

示例

示例 1

输入：root = [1,2,2,3,4,4,3]
输出：True

示例 2

输入：root = [1,2,2,null,3,null,3]
输出：False

方法一：递归判断

解题步骤

1. 基本情况：如果两个节点都是 None，返回 True；一个是 None 另一个不是，返回 False。
2. 比较节点：比较当前两节点的值，如果不相等，返回 False。
3. 递归比较：递归比较左子树的左孩子和右子树的右孩子，以及左子树的右孩子和右子树的左孩子。

Python 示例

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

def isSymmetric(root):
    """
    判断二叉树是否对称
    :param root: TreeNode, 二叉树的根节点
    :return: bool, 是否对称
    """
    def isMirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return left.val == right.val and isMirror(left.left, right.right) and isMirror(left.right, right.left)
    
    return isMirror(root, root)

# 示例调用
root = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))
print(isSymmetric(root))  # 输出: True

算法分析

• 时间复杂度：(O(n))，其中 (n) 是树中节点的数量，因为需要访问树中的每一个节点。
• 空间复杂度：(O(h))，其中 (h) 是树的高度，空间消耗来自递归的栈空间。

方法二：迭代使用队列

解题步骤

1. 初始化队列：将根节点的两份加入队列。
2. 迭代比较：每次从队列中取出两个节点并比较它们。
3. 子节点入队：如果节点相同，则将它们的子节点按对称顺序加入队列。

Python 示例

from collections import deque

def isSymmetric(root):
    """
    使用队列迭代判断二叉树是否对称
    :param root: TreeNode, 二叉树的根节点
    :return: bool, 是否对称
    """
    queue = deque([root, root])
    while queue:
        t1, t2 = queue.popleft(), queue.popleft()
        if not t1 and not t2:
            continue
        if not t1 or not t2 or t1.val != t2.val:
            return False
        queue.append(t1.left)
        queue.append(t2.right)
        queue.append(t1.right)
        queue.append(t2.left)
    return True

# 示例调用
root = TreeNode(1, TreeNode(2, None, TreeNode(3)), TreeNode(2, None, TreeNode(3)))
print(isSymmetric(root))  # 输出: False

算法分析

• 时间复杂度：(O(n))，因为需要访问每个节点。
• 空间复杂度：(O(n))，在最坏的情况下，队列中需要存储所有节点。

方法三：使用栈进行迭代

解题步骤

1. 使用栈：将根节点的两份压入栈中。
2. 迭代比较：从栈中弹出两个节点并进行比较。
3. 子节点压栈：如果节点相同，则将它们的子节点按对称顺序压入栈中。

Python 示例

def isSymmetric(root):
    """
    使用栈迭代判断二叉树是否对称
    :param root: TreeNode, 二叉树的根节点
    :return: bool, 是否对称
    """
    if not root:
        return True
    stack = [(root.left, root.right)]
    while stack:
        left, right = stack.pop()
        if not left and not right:
            continue
        if not left or not right or left.val != right.val:
            return False
        stack.append((left.left, right.right))
        stack.append((left.right, right.left))
    return True

# 示例调用
root = TreeNode(1, TreeNode(2, None, TreeNode(3)), TreeNode(2, None, TreeNode(3)))
print(isSymmetric(root))  # 输出: False

算法分析

• 时间复杂度：(O(n))，需要访问每个节点。
• 空间复杂度：(O(n))，在最坏的情况下，栈中需要存储所有节点。

不同算法的优劣势对比

应用示例

这些方法可以用于计算机视觉中对象的对称性检测，软件测试中的树结构数据验证，或者在机器学习数据预处理中检查数据的对称性。