A tree is symmetric if the left subtree is a mirror reflection of the right subtree. If the left subtree is a mirror reflection of the right subtree, two subtrees should have same root value. The left subtree of left subtree should also be a mirror reflection of the right subtree of right subtree.
Solution 1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
return self.isMirror(root, root) #can not use (left,right). Should make sure the root is not None
def isMirror(self, left, right) -> bool:
if left is None and right is None:
return True
elif left is None or right is None or left.val != right.val:
return False
else:
return self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)
We compare every pair of nodes. Time complexity is O(n). n is the number of nodes. Space complexity is O(n). The number of recursive calls is bound by the height of tree. n is the hight of tree.
步步发财 