Mar 20, 2021

Leetcode 100 Same Tree

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.

image 
Input: p = [1,2,3], q = [1,2,3]
Output: true
image 
Input: p = [1,2], q = [1,null,2]
Output: false
image 
Input: p = [1,2,1], q = [1,1,2]
Output: false
  • Bu problemde bizden istenen 1. ve 2. ağacın tamamen aynı olmasıdır.
  • İlk olarak kökleri kontrol ederiz.İkisi de boş ise true döneriz.
  • Eğer kökler var ise, köklerdeki değerlerin eşit olup olmadığını kontrol ederiz.Temel kontrollerimizi tamalamış olduk.
  • Bu noktadan sonra bu kontrolleri tüm node larda yapmamız gerekmektedir.Bunun için DFS kullanılan recursive çağırma yöntemi ile sağ ve sol dallardaki tüm node ları çağırarak kontrol ederiz.
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p is None and q is None:   #kökler dolu mu ?
            return True

        if p is None or q is None or p.val != q.val: kökler dolu ise #kökler dolu ve değerler eşit mi?
            return False
        
        #tüm node lar için tekrar tekrar çağır.
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)