MUYANG GUO / INDEX

LeetCode

LeetCode 100 Same Tree - Easy

100. Same Tree -- Easy

·1 min read·#LeetCode#Easy#Python

100. Same Tree — Easy

Open on LeetCode

Problem

  1. Same Tree -- Easy

Given two binary trees, 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: 1 1 / \ /
2 3 2 3

    [1,2,3],   [1,2,3]

Output: true

Example 2: Input: 1 1 /
2 2

    [1,2],     [1,null,2]

Output: false

Example 3: Input: 1 1 / \ /
2 1 1 2

    [1,2,1],   [1,1,2]

Output: false

Solution

# Recursion:
# 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: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
 
# Iterative:
from collections import deque
class Solution:
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """    
        def check(p, q):
            # if both are None
            if not p and not q:
                return True
            # one of p and q is None
            if not q or not p:
                return False
            if p.val != q.val:
                return False
            return True
        
        deq = deque([(p, q),])
        while deq:
            p, q = deq.popleft()
            if not check(p, q):
                return False
            
            if p:
                deq.append((p.left, q.left))
                deq.append((p.right, q.right))
                    
        return True

Comments