[Leetcode]100. Same Tree

📄 Description

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

💻 My Submission - BFS

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        queue=[]
        queue.append((p,q))
        
        while queue:
        	p1,q1=queue.pop(0)
            if not p1 and not q1:
		        continue
            elif None in [p1,q1]:
                return False
            else:
                if p1.val!=q1.val:
                    return False
                queue.append((p1.left,q1.left))
                queue.append((p1.right,q1.right))     
        return True

Other Solutions (1) DFS using stack

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        stack=[]
        stack.append((p,q))
        
        while stack:
            p1,q1=stack.pop()
            if not p1 and not q1:
                continue
            elif None in [p1,q1]:
                return False
            else:
                if p1.val!=q1.val:
                    return False
                stack.append((p1.right,q1.right))     
                stack.append((p1.left,q1.left))          
        return True

Other Solutions (2) Recursion

	def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if p and q and p.val==q.val:
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        return False

💡 What I learned

1. How to check if one of two is None

if None in [p1,q1]:

2. How DFS using stack and BFS using queue is different?

• the order you add to stack/queue
• whether you pop off the left(pop(0)) or the rightmost(pop()) element.

(1) DFS

• pop off the left element
• add to stack right node, then left node

stack.pop()
...
stack.append((p1.right, q1.right))
stack.append((p1.left, q1.right))

(2) BFS

• pop off the rightmost element
• add to queue left node, then right node

queue.pop(0)
...
queue.append((p1.left, q1.right))
queue.append((p1.right, q1.right))

References
https://leetcode.com/problems/same-tree/
https://leetcode.com/problems/same-tree/discuss/32894/Python-Recursive-solution-and-DFS-Iterative-solution-with-stack-and-BFS-Iterative-solution-with-queue