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、题目描述
给定一个二叉树,检查它是否是镜像对称的。
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错误与测试