python数据结构（对称二叉树递归和迭代）

1、题目描述

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

2、代码详解

2.1 递归写法

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

class Solution(object):
    # 递归写法
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.isMirror(root, root)

    def isMirror(self, root1, root2):
        # 递归结束条件
        if not root1 and not root2:  # 条件1：都为空指针则返回 true
            return True
        elif not root1 or not root2:  # 条件2：只有一个为空则返回 false
            return False

        return (root1.val == root2.val) and \
               self.isMirror(root1.left, root2.right) and \
               self.isMirror(root1.right, root2.left)

pNode1 = TreeNode(1)
pNode2 = TreeNode(2)
pNode3 = TreeNode(2)
pNode4 = TreeNode(3)
pNode5 = TreeNode(4)
pNode6 = TreeNode(4)
pNode7 = TreeNode(3)

pNode1.left = pNode2
pNode1.right = pNode3
pNode2.left = pNode4
pNode2.right = pNode5
pNode3.left = pNode6
pNode3.right = pNode7

S = Solution()
print(S.isSymmetric(pNode1))  # True 

时间复杂度是 O(n)，因为要遍历 n 个节点

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

2.2 迭代写法

用队列来实现

• 首先从队列中拿出两个节点(left 和 right)比较
• 将 left 的 left 节点和 right 的 right 节点放入队列
• 将 left 的 right 节点和 right 的 left 节点放入队列

时间复杂度是 O(n)，空间复杂度是 O(n)

class Solution(object):
	def isSymmetric(self, root):
		"""
		:type root: TreeNode
		:rtype: bool
		"""
		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 

本文地址：https://blog.csdn.net/IOT_victor/article/details/107117445