Solution to LeetCode 100 Same Tree, LeetCode 101 Symmetric Tree, and LeetCode 572 Subtree of Another Tree.
LeetCode 100
Same Tree (Easy) [link]
Same idea as LC101, but check whether they are the same rather than checking whether they are mirror.
1] Recursive solution. DFS. Time complexity O(min(n,m)). Space complexity O(min(m,n)).
# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p == None and q == None:
return True
elif p == None or q == None or q.val != p.val:
return False
else:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
We don’t need to define another recursion function within isSameTree, because isSameTree also works on smaller subtrees.
2] Iterative solution using Queue. BFS. Time complexity O(min(n,m)). Space complexity O(min(m,n)).
# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
que = deque()
que.append(p)
que.append(q)
while que:
first = que.popleft()
second = que.popleft()
if not first and not second:
continue
if not first or not second or first.val != second.val:
return False
que.append(first.left)
que.append(second.left)
que.append(first.right)
que.append(second.right)
return True
3] Iterative solution using stack. Time complexity O(min(n,m)). Space complexity O(min(m,n)).
# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
stack = []
stack.append(p)
stack.append(q)
while stack:
first = stack.pop()
second = stack.pop()
if not first and not second:
continue
if not first or not second or first.val != second.val:
return False
stack.append(first.left)
stack.append(second.left)
stack.append(first.right)
stack.append(second.right)
return True
LeetCode 101
Symmetric Tree (Easy) [link]
1] Recursive solution. In the following cases, we return False: 1) left != None and right == None 2) left == None and right != None 3) left.val != right.val. we return True if left == None and right == None. Those are the stopping criteria. Otherwise, we return True. When comparing the children in the same level, we return True if all of the following are satisfied 1) left.left == right.right 2) left.right == right.left. Otherwise, we return False. Time complexity O(n). Space complexity O(n).
# 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: Optional[TreeNode]) -> bool:
if not root:
return False
def compare(left,right):
if left == None and right == None:
return True
elif left == None or right == None or left.val != right.val:
return False
outside = compare(left.left, right.right)
inside = compare(left.right, right.left)
return outside and inside
return compare(root.left, root.right)
There has to be a function defined within isSymmetric because we are not comparing two children of a node, rather, we are comparing between the children belonging to different parent.
2] Iterative solution using Queue. Time complexity O(n). Space complexity O(n).
# 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: Optional[TreeNode]) -> bool:
if not root:
return False
que = deque()
que.append(root.left)
que.append(root.right)
while que:
left = que.popleft()
right = que.popleft()
if not left and not right:
continue
if not left or not right or left.val != right.val:
return False
que.append(left.left)
que.append(right.right)
que.append(left.right)
que.append(right.left)
return True
3] Iterative solution using Stack. Same idea as [2]. Time complexity O(n). Space complexity O(n).
# 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: Optional[TreeNode]) -> bool:
if not root:
return False
stack = []
stack.append(root.left)
stack.append(root.right)
while stack:
left = stack.pop()
right = stack.pop()
if not left and not right:
continue
if not left or not right or left.val != right.val:
return False
stack.append(left.left)
stack.append(right.right)
stack.append(left.right)
stack.append(right.left)
return True
LeetCode 572
Subtree of Another Tree (Easy) [link]
We check whether subRoot is the same as any subtree of the root. The checking method is the same as in LC 100. Here we check every subtree of root with subRoot. Note that both isSubtree and isSameTree functions are recursive function, so both need stopping criteria. Time complexity O(pq). Space complexity O(max(p,q)).
# 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 isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
def isSameTree(p, q):
if not p and not q:
return True
elif not p or not q:
return False
return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
if not root and not subRoot:
return True
elif not root or not subRoot:
return False
return isSameTree(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot
