1、题目描述

https://leetcode-cn.com/problems/symmetric-tree/

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

相似题：剑27. 二叉树的镜像  https://mp.csdn.net/console/editor/html/90676859

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

https://leetcode-cn.com/problems/symmetric-tree/solution/hua-jie-suan-fa-101-dui-cheng-er-cha-shu-by-guanpe/

时间复杂度是 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://leetcode-cn.com/problems/symmetric-tree/solution/dong-hua-yan-shi-101-dui-cheng-er-cha-shu-by-user7/