欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

python数据结构(对称二叉树递归和迭代)

程序员文章站 2022-10-19 12:57:57
1、题目描述https://leetcode-cn.com/problems/symmetric-tree/给定一个二叉树,检查它是否是镜像对称的。2、代码详解2.1 递归写法# Definition for a binary tree node.class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right =...

1、题目描述

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

python数据结构(对称二叉树递归和迭代)python数据结构(对称二叉树递归和迭代)

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

相关标签: python