Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3]
is symmetric:
1 / 2 2 / / 3 4 4 3
But the following [1,2,2,null,3,null,3]
is not:
1 / 2 2 3 3
判断一棵树是否对称
递归:
1 class Solution(object): 2 def isSymmetric(self, root): 3 if not root: 4 return True 5 return self.issym(root.left,root.right) 6 def issym(self,left,right): 7 if not left and not right: 8 return True 9 if not left or not right: 10 return False 11 if left.val == right.val: 12 return self.issym(left.left,right.right) and self.issym(left.right,right.left) 13 return False
非递归:
递归本质上就是栈,所以。。。
1 class Solution(object): 2 def isSymmetric(self, root): 3 if not root: 4 return True 5 stack=[[root.left,root.right]] 6 while stack: 7 left,right = stack.pop() 8 if not left and not right: 9 continue 10 if not left or not right: 11 return False 12 if left.val == right.val: 13 stack.append([left.right,right.left]) 14 stack.append([left.left,right.right]) 15 else: 16 return False 17 return True