class Solution: # @param root, a tree node # @return a boolean def isSymmetric(self, root): # a new recursive function to check if two tree are symetric def isMirror(root1,root2): # they all could be Null to be symetric if not root1 and not root2: return True # if they are not Null, they must carry the same value elif (root1 and root2) and root1.val==root2.val: # recursively call itself return isMirror(root1.left,root2.right) and isMirror(root1.right, root2.left) else: return False if not root: return True return isMirror(root.left, root.right)
class Solution: # @param root, a tree node # @return a boolean def isSymmetric(self, root): if not root : return True queue=[[root.left,root.right]] # use a queue to store nodes. Each element in the queue is a pair of nodes. They are supposed to carry the same value. Ortherwise, the tree is not symetric while queue: pair=queue.pop(0) if not (pair or pair): # if current pair are empty, do nothing continue elif (pair and pair) and pair.val==pair.val: # if current pair carry the same value, push the their children pairs into the queue queue.append([pair.left,pair.right]) queue.append([pair.right,pair.left]) else: return False # if all pairs pass the evaluation, the tree is symmetric return True
Any comments would be appreciated!
Thanks for the comments. Actually the "queue" is a queue. I use queue.pop(0) to pop the first element in the list instead of the newly appended element. Thus it is a queue.
Sorry, my Implementation use "pop()" not "pop(0)", so I ignored the zero. Use python list as a queue has performance problem that every time pop a element for top of a python list, the runtime would have to move all elements after first one one step ahead. This has a O(n) time complexity.
https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt Here is a summary of most python function time complexity.
Thank you @sheehan for sharing. It's of great help to me. Though pop(0) will have O(n) complexity, all test cases seem to be fine with my submission. Do you mind to share your implementation with stack?
This basically is similar to your code with small optimization
class Solution: def check_symmetry(self, node1, node2): if not node1 and not node2: return True elif not node1 or not node2: return False return (node1.val == node2.val and self.check_symmetry(node1.left, node2.right) and self.check_symmetry(node1.right, node2.left))
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.