LC 0101 [E] Symmetric Tree
Code with Senpai edited this page Feb 4, 2022
·
4 revisions
T: O(b)
S: O(logn)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSymmetric(self, root):
def isMirror(left, right):
if not left and not right: # no subtrees
return True
if not left or not right: # one subtree is missing
return False
if left.val == right.val:
outer = isMirror(left.left, right.right)
inner = isMirror(left.right, right.left)
return outer and inner
else: # different values
return False
if not root:
return True
else: # check subtrees
return isMirror(root.left, root.right)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSymmetric(self, root):
if not root:
return True
stack = [ (root.left, root.right) ]
while stack:
left, right = stack.pop()
if not left and not right:
continue
if not left or not right:
return False
if left.val == right.val:
stack.append( (left.left, right.right) )
stack.append( (left.right, right.left) )
else:
return False
return True
footer