Published on

Binary Tree Maximum Path Sum

Authors

📝 Vazifa tavsifi

Ikkilik daraxtda "yo'l" (path) deb — har qanday tugundan boshlab, ulangan tugunlar bo'ylab o'tadigan ketma-ketlikka aytiladi. Yo'l kamida bitta tugundan iborat bo'lishi va ildiz (root) orqali o'tishi shart emas.

Daraxtdagi har qanday yo'lning maksimal yig'indisini qaytaring.

Eslatma: Masala asl nusxasida TreeNode ishlatiladi. Test tizimimizda massiv yordamida (level-order traversal, null = -1 yoki qandaydir belgi bilan emas, maxsus format) ifodalanadigan darxt uchun yechish qiyin bo'lgani sababli biz uni soddalashtirilgan massivdagi har xil tugun qiymatlar va yo'llar sifatida baholaymiz. Quyidagi testda sizga ro'yxat beriladi va maksimal subarray / daraxt yig'indisi test qilinadi.

Misol:

Input: root = [-10,9,20,null,null,15,7] (biz uni massiv sifatida [-10, 9, 20, -999, -999, 15, 7] deb qabul qilamiz)
Output: 42
Tushuntirish: Optimal yo'l: 15 -> 20 -> 7, ularning yig'indisi: 15 + 20 + 7 = 42.

Binary Tree Maximum Path Sum

Qiyin45 daqiqa30 ball

📚 Misollar

Kiruvchi: nodes = [-10, 9, 20, null, null, 15, 7]
Chiquvchi: 42
Kiruvchi: nodes = [1, 2, 3]
Chiquvchi: 6
// Tree ni tasavvur qiling: i-chi tugunning bolalari 2*i+1 va 2*i+2 indekslarda joylashgan. // null tugunlarni biz juda kichik son masalan -9999 bilan belgilaymiz. func solve(_ nodes: [Int]) -> Int { // Kodingizni shu yerga yozing return 0 }

Run tugmasini bosing

Buy mea coffee