[Leetcode]100. Same Tree

13415 ワード
leetcode BFS tree linked list DFS recursion テキストリンク

📄 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
    javax.persistence.MappedSuperclass
    3/21学習問題