Mar 24, 2021

Leetcode 572 Subtree of Another Tree

Soru

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.

Örnek 1

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

Örnek 2

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

Çözüm DFS

  • Bu soru, bir ikili ağacın (root) içinde, verilen başka bir ağacın (subRoot) olup olmadığını kontrol etmeyi gerektirir.

  • İki yardımcı fonksiyon kullanırız:

  • isSameTree(p, q) → p ve q ağaçlarının tamamen aynı olup olmadığını kontrol eder.

  • isSubtree(root, subRoot) → root ağacının her düğümünü dolaşarak subRoot ile eşleşen bir düğüm olup olmadığını kontrol eder.

  • Adımlar:

  • root düğümüne bakarız, eğer root ile subRoot birebir aynıysa True döndürürüz.

  • Eğer eşleşme yoksa root’un sol ve sağ alt ağaçlarında subRoot olup olmadığını kontrol ederiz.

  • Alt ağaçları rekürsif olarak tarayarak çözümü tamamlarız.

Code

   class Solution:
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        if not root:
            return False  # root None olduysa, subRoot bulunamaz.
        
        if self.isSameTree(root, subRoot):  
            return True  # Eğer root ile subRoot tamamen aynıysa True döndür
        
        # Alt ağaçlarda aramaya devam et (sol ve sağ alt ağaçlar)
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True  # İkisi de None ise aynı
        if not p or not q or p.val != q.val:
            return False  # Biri None veya değerleri farklıysa farklı
        
        # Sol ve sağ alt ağaçları da karşılaştır
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Complexity

  • Time complexity (Zaman Karmaşıklığı): O(m * n) (Her düğümde isSameTree çağrıldığı için)
  • Space complexity (Alan Karmaşıklığı): O(n) (Recursive çağrılar için çağrı yığını kullanılır)