It’s an easy LeetCode problem, and the description is concise and straightforward. We can solve this problem using the DFS algorithm.
From two binary trees, we have to check whether both are the same or not.
Consider the following cases for two different nodes.
- If both nodes are null, we can say that both nodes are the same.
- If one node is null and the other is not, we can return False because they are not the same.
- If two nodes’ values are different, that’s not the same, and we can return False.
Take the above cases as base cases for the DFS algorithm. If then, we are almost near to the solution. The remaining part is the recursive case. There are two simple recursive cases. One is for continuously going to the left of both trees, and another one is going to the right.
dfs(tree1.left, tree2.left)
dfs(tree1.right, tree2.right)Based on the base cases, we will get True or False. So, end of the recursion, we will get our final answer. And we will return it.
True/False <= dfs(tree1.left, tree2.left) && dfs(tree1.right, tree2.right)Let’s see the solution in code for better understanding.
# 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 not p and not q:
return True
if not p or not q or p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)