【LeetCode】101. 对称二叉树

一、题目描述

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

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

进阶：

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

二、解题思路 & 代码

2.1 递归

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
                return True
        def dfs(left,right):
            # 递归的终止条件是两个节点都为空
            # 或者两个节点中有一个为空
            # 或者两个节点的值不相等
            if not (left or right):
                return True
            if not (left and right):
                return False
            if left.val!=right.val:
                return False
            return dfs(left.left,right.right) and dfs(left.right,right.left)
        # 用递归函数，比较左节点，右节点
        return dfs(root.left,root.right)

时间复杂度 O(n)，因为要遍历 n 个节点
空间复杂度 O(n)，空间复杂度是递归的深度，也就是跟树高度有关，最坏情况下树变成一个链表结构，高度是 n。

2.2 队列实现

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
	def isSymmetric(self, root):
		if not root or not (root.left or root.right):
			return True
		# 用队列保存节点 
		queue = [root.left,root.right]
		while queue:
			# 从队列中取出两个节点，再比较这两个节点
			left = queue.pop(0)
			right = queue.pop(0)
			# 如果两个节点都为空就继续循环，两者有一个为空就返回false
			if not (left or right):
				continue
			if not (left and right):
				return False
			if left.val!=right.val:
				return False
			# 将左节点的左孩子， 右节点的右孩子放入队列
			queue.append(left.left)
			queue.append(right.right)
			# 将左节点的右孩子，右节点的左孩子放入队列
			queue.append(left.right)
			queue.append(right.left)
		return True

复杂度分析

时间复杂度：O(n)，同「方法一」。
空间复杂度：O(n)，这里需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过 n 个点，故渐进空间复杂度为 O(n)。

参考：

LeetCode题解