python-leetcode38.翻转二叉树

题目：

给定一个二叉树的根节点root,检查它是否轴对称。

---

方法一：递归

如果一个树的左子树与右子树镜像对称，那么这个树是对称的。

互为镜像的条件：他们的两个根结点具有相同的值，每棵树的右子树都与另一个树的左子树镜像对称

可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，p指针和q指针一开始都指向这棵树的根，随后p右移时，q左移，p左移时，q右移。每次检查当前p和q节点的值是否相等，如果相等再判断左右子树是否对称。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def isSymmetric(self, root): """ :type root: Optional[TreeNode] :rtype: bool """ return self.check(root.left,root.right) def check(self,p,q): if p is None and q is None: return True if p is None or q is None: return False return p.val==q.val and self.check(p.left,q.right) and self.check(p.right,q.left)

时间复杂度：O(n)

空间复杂度：O(n)

---

方法二：迭代

初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def isSymmetric(self, root): """ :type root: Optional[TreeNode] :rtype: bool """ return self.check(root,root) #同一个根节点是因为要比较树的左右子树 def check(self,u,v): q=[] #将节点 u 和 v（即左右子树的根节点）添加到队列中，接下来我们将对这些节点进行比较 q.append(u) q.append(v) while q: u=q.pop(0) v=q.pop(0)#每次从队列中取出两个节点比较，看它们是否对称 if u is None and v is None:#如果都是 None，说明这两个子树都为空，可以跳过这次比较 continue if u is None or v is None or u.val !=v.val: return False q.append(u.left) #节点 u 和 v 的子节点按照对称的方式加入队列 q.append(v.right) q.append(u.right) q.append(v.left) return True

时间复杂度：O(n)

空间复杂度：O(n)