İçeriğe geç

Kökten yaprağa hedef toplam

Kolay#dfs#recursion~20 dk

Görev tanımı

Problem

İkili bir ağaç ve bir hedef sayı verildiğinde, kökten bir yaprağa inen bir yolun değerlerinin toplamının tam olarak hedefe eşit olup olmadığına karar ver. Yaprak çocuğu olmayan bir düğümdür; yani bir yol her zaman ağacın dibinde bitmelidir. Değerler negatif olabilir.

Örnekler

Input:  tree = 5, left 4 with left child 11 having children 7 and 2,
        right 8 with children 13 and 4; target = 22
Output: True
Neden: 5, 4, 11, 2 yolunun toplamı 22
Input:  tree = 1 with a single left child 2; target = 1
Output: False
Neden: kök bir yaprak değil, bu yüzden yol orada duramaz
Input:  tree = empty; target = 0
Output: False
Neden: edge case: boş bir ağacın hiç kökten yaprağa yolu yok

İpuçları

0 / 3

Hedef zaman
O(n)
Hedef alan
O(h)

Kısıtlar

  • values may be negative
  • a path must end at a leaf

Kodda değil de fikirde mi takıldın? Path Sum varyantları bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır