https://leetcode-cn.com/problems/symmetric-tree/
给定一个二叉树，检查它是否是镜像对称的。
相似题：剑27. 二叉树的镜像 https://mp.csdn.net/console/editor/html/90676859
我要评论
# 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。
用队列来实现
时间复杂度是 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知识点：函数参数、迭代器、生成器、装饰器、函数式变成、map/reduce、filter、sorted、继承和多态
qt designer 关于多页面跳转之后同一个页面出现多次的问题
网友评论