[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