问题描述：
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1 / \ 2 2 / \ / \3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1 / \ 2 2 \ \ 3 3
方法1：用两个列表模拟栈，初始a栈和b栈分别存储根节点的左节点和右节点，此后，a的左孩子进栈a,b的右孩子进栈b，a的右孩子进栈a,b的左孩子进栈b。出栈时进行比较，如果不相等则返回False
1 class Solution(object): 2 def isSymmetric(self, root): 3 """ 4 :type root: TreeNode 5 :rtype: bool 6 """ 7 if not root: 8 return True 9 stacka, stackb = [root.left], [root.right]10 while stacka and stackb:11 a = stacka.pop()12 b = stackb.pop()13 if not a and not b:14 continue15 16 elif not a or not b:17 return False18 elif a.val != b.val:19 return False20 else:21 stacka.append(a.left)22 stackb.append(b.right)23 stacka.append(a.right)24 stackb.append(b.left)25 if stacka or stackb:26 return False27 else:28 return True
方法2：
1 class Solution(object): 2 def isSymmetric(self, root): 3 """ 4 :type root: TreeNode 5 :rtype: bool 6 """ 7 if root==None: 8 return True 9 if root.left and root.right:10 if root.left.val!=root.right.val:11 return False12 13 l_list=[]14 r_list=[]15 def preVisit(self,root):16 if root==None:17 l_list.append(None)18 return19 if root.left==None and root.right==None:20 l_list.append(root.val)21 return22 preVisit(self,root.left)23 l_list.append(root.val)24 preVisit(self,root.right)25 26 def postVisit(self,root):27 if root==None:28 r_list.append(None)29 return30 if root.left==None and root.right==None: 31 r_list.append(root.val)32 return33 34 postVisit(self,root.right)35 r_list.append(root.val)36 postVisit(self,root.left)37 38 preVisit(self,root.left)39 postVisit(self,root.right)40 # print(l_list)41 # print(r_list)42 return l_list==r_list
l_list=[5,3,6,2,6,4,8]
r_list=[5,3,6,2,6,4,8]
方法3：
1 class Solution(object): 2 def isSymmetric(self, root): 3 """ 4 :type root: TreeNode 5 :rtype: bool 6 """ 7 def helper(root,mirror): 8 if not root and not mirror: 9 return True10 if root and mirror and root.val == mirror.val:11 return helper(root.left,mirror.right) and helper(root.right,mirror.left)12 return False13 return helper(root,root)
2018-09-07 19:51:41