Leetcode 112 Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true

Input: root = [1,2,3], targetSum = 5
Output: false

Input: root = [1,2], targetSum = 0
Output: false

• Bize bir ikili ağaç ve bir toplam verilmektedir.Bu ikili ağaçtaki kökten(root) yaprağa(leaf) uzanan bir daldaki değerlerin toplamı bize verilen toplam değere eşit ise true.Hiç bir dalın toplamı bu değere eşit değil ise false dönmemiz beklenmektedir.
• DFS yaklaşımı ile bu problemi çözebiliriz.
• DFS işlemine ağacın kökü(root) ile başlarız.
• Eğer elimizdeki node yaprak(leaf) değil ise, iki işlem yaparız:
  • Yeni bir toplam(S) bulmak için mevcut düğümün değerini(node.value) önceki toplamdan(S) çıkarırız => S = S - node.value
  • Elimizdeki node un her iki çocuğu içinde recursive çağrılar yaparız ve önceki adımdaki gibi yeni toplamlar hesaplarız.
• Her adımda, ziyaret edilen node yaprak(leaf) node mu diye kontrol ederiz ve onun değeri elimizdeki toplama(S) eşit mi diye kontrol ederiz. Her koşul sağlanıyorsa true döneriz,aradığımız dalı bulmuşuzdur.
• Eğer bulduğumuz node leaf ama değeri elimizdeki toplama(S) eşit değil ise, false döneriz.

    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        if root is None:
            return False
        if root.val == targetSum and root.left is None and root.right is None:
            return True
        return self.hasPathSum(root.left,targetSum - root.val) or 
               self.hasPathSum(root.right,targetSum - root.val)