Leetcode 572 Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

• Burada bize 2 ağaç veriliyor ve bu ağaçlardan 2. sinin 1. ağaç içerisinde birebir aynı olarak yer alıyor mu bulmamız isteniyor.
• Sorunun çözümünde Leetcode 100 Same Tree kullandığımız algoritmadan yararlanabiliriz.
• Leetcode 100 sorusunda 2 ağaçta birebir aynı mı diye kontrol ederken bu sefer kökten başlayarak tüm ağacı dolaşıp 1. ağaç içinde 2. ağacın birebir aynısı var mı diye arayacağız.
• s 1. ağacın kökü ve t 2. ağacın kökü olarak leetcode 100 ün çözümü olan isSame fonksiyonuna gönderilir.
• isSame fonksiyonu da kendi içinde recursive olarak bu iki ağacın aynı olup olmadığını kontrol eder.
• Eğer isSame fonksiyonundan True dönmez ise 1. ağacın (s) child nodeları için recursive olarak isSubtree çağrılır.
• Bu şekilde birebir aynı bir ağaç bulunana kadar işlem devam eder.Bulamaz ise false döner.

   def isSubtree(self, s, t):
        if s == None:
            return False
        if self.isSame(s, t):
            return True
        return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
    
    
    def isSame(self, s, t):
        if s == None and t == None:
            return True
        if s == None or t == None:
            return False
        if s.val != t.val:
            return False
        return self.isSame(s.left, t.left) and self.isSame(s.right, t.right)