Path Sum II LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Facebook google microsoft
İndi Xidmət Walmart Qlobal texnologiyaBaxılıb 21

Problem bəyanat :

Path Sum II LeetCode Solution – Nəzərə alınmaqla root bir ikili ağac və tam ədəd targetSum, qayıt hər kökdən yarpağa yoldakı node dəyərlərinin cəminin bərabər olduğu yollar targetSum. Hər bir yol qovşağın siyahısı kimi qaytarılmalıdır dəyərlər, node istinadları deyil.

kökdən yarpağa yol kökdən başlayan və istənilən yarpaq düyünündə bitən yoldur. A yarpaq uşaqları olmayan bir düyündür.

Path Sum II LeetCode HəlliPin

 

Yanaşma:

İdeya:

Beləliklə, burada nələrimiz var ...
Bizə a kökü verilir İkili ağac və biz kökdən yarpağa bərabər olan yol cəmini tapmalıyıq hədəf cəmi (verilir). Beləliklə, bunu həll etmək üçün ağacların dərinliyinə getməliyik. Biz izləyəcəyimiz ən sadə Asan yanaşma.

İzahat:

plan belədir:

Hər bir mümkün nodu keçəcəyik və rejim dəyərini ondan çıxaracağıq hədəf cəmi. Əgər yarpaq düyününə çatsaq, onun sıfır olub-olmadığını yoxlayacağıq.

1. Bizdən cari yolu saxlamaq üçün “yol” massivi və problemin yekun cavabını saxlamaq üçün başqa “res” massivi tələb olunacaq.
2. Traversimizə kökdən başlayırıq. Dəyərini azaldın hədəf cəmi və həmçinin "yol" massivinə dəyəri əlavə edin, çünki kökdən yarpaq yolu qaytarmalıyıq.
3 . Sonra daha da dərinləşəcəyik; həm uşağı istifadə edərək: sola və sağa və həmin node dəyərindən çıxın hədəf cəmi  və həmçinin hər hansı yarpaq qovşağına çatana qədər yol massivinə əlavə edirik (Node uşaq yoxdur)

4. İstənilən yarpaq düyününə çatdıqda, cari node dəyərini ondan çıxarmalıyıq hədəf cəmi və yoxlayın hədəf cəmi sıfıra çevrilir ya yox.
belədirsə, yolu (massiv) res massivinə saxlayın. yoxsa... heç nə etmə.

Və keçid davam edir.

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        def dfs(root,targetSum,path):
            if not root :
                return 
            if root.left is None and root.right is None and targetSum - root.val == 0 :
                res.append(path + [root.val])
            dfs(root.left,targetSum - root.val , path + [root.val])
            dfs(root.right,targetSum - root.val , path + [root.val])
        dfs(root,targetSum,[])
        return res

 

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if(root == null)
            return res;
        dfs(root, targetSum, new ArrayList<>());
        return res;
    }

    void dfs(TreeNode node, int targetSum, ArrayList<Integer> path) {
        if(node == null)
            return;
            path.add(node.val);
            targetSum -= node.val;
        
        if(targetSum == 0 && node.left == null && node.right == null)
            res.add(path);
        
        dfs(node.left, targetSum, new ArrayList<>(path));
        dfs(node.right, targetSum, new ArrayList<>(path));
    }
}

Path Sum II LeetCode Həlli üçün Mürəkkəblik Təhlili:

Necə ki, hər bir qovşağı ziyarət etdik Zamanın mürəkkəbliyi olacaq O (n)

və biz yolu saxlayırıq. belə ki, xərc əlavə yer of O (n) həmçinin.

Bu belədir. kod edilir.

Qeyd: python həllində mən Nested Function istifadə etmişəm.

Translate »