Mar 20, 2021

Leetcode 100 Same Tree

Soru

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.

Örnek 1

image 
Input: p = [1,2,3], q = [1,2,3]
Output: true

Örnek 2

image 
Input: p = [1,2], q = [1,null,2]
Output: false

Örnek 3

image 
Input: p = [1,2,1], q = [1,1,2]
Output: false

Çözüm DFS

  • Bu problem, iki ikili ağacın tamamen aynı olup olmadığını kontrol etmemizi istiyor.
  • Girdi:p ve q adlı iki ikili ağacın kök düğümleri.
  • Çıktı:Eğer iki ağaç birebir aynıysa True, değilse False.
  • İki ağaç aynı kabul edilir eğer:Düğümler aynı konumda olmalı (yapı aynı olmalı).Düğümlerin değerleri aynı olmalı.
  • Bu problemi özyinelemeli (recursive) DFS ile çözebiliriz.
  • İki ağacı eşzamanlı olarak gezerek:
  • Eğer her iki düğüm de None ise, True döndür.
  • Eğer biri None, diğeri değilse, False döndür.
  • Eğer değerleri eşleşmiyorsa, False döndür.
  • Sol ve sağ alt ağaçları aynı şekilde karşılaştır.

Code

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:  # İkisi de None ise aynı
            return True
        if not p or not q:  # Biri None, diğeri değilse farklı
            return False
        if p.val != q.val:  # Değerleri farklıysa farklı
            return False
        # Sol ve sağ alt ağaçları 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(n).
  • Space complexity (Alan Karmaşıklığı): O(h) h → Ağacın yüksekliği.Eğer ağaç dengeli (balanced) ise, her seviye düğüm sayısını yarıya böler.Bu durumda, ağacın yüksekliği O(log n) olur.Eğer ağaç tek taraflı (linked list gibi) uzuyorsa, h = n olur.