<prompt> njia katika mti wa binary ni mfuatano wa nodi ambapo kila jozi ya nodi zilizo karibu katika mfuatano huo zina ukingo unaoziunganisha. Nodi inaweza tu kuonekana katika mfuatano mara moja. Kumbuka kwamba njia haina haja ya kupita kwenye mizizi.Jumla ya njia ya njia ni jumla ya maadili ya nodi kwenye njia.Kwa kuzingatia mzizi wa mti wa jozi, rudisha _kiwango cha juu kabisa cha njia ya njia yoyote isiyo tupu_.Mfano wa 1:Ingizo: mzizi 1,2,3Pato: 6Maelezo: Njia mojawapo ni 2 - 1 - 3 yenye jumla ya njia ya 2 1 3 6.Mfano wa 2:Ingizo: mzizi -10,9,20,null,null,15,7Pato: 42Maelezo: Njia mojawapo ni 15 - 20 - 7 yenye jumla ya njia 15 20 7 42.Vikwazo: Idadi ya nodi kwenye mti iko katika safu 1, 3 104. -1000 Node.val 1000  <response>: chatudarasa TreeNode: def __init__binafsi, val0, leftNone, rightNone: self.val val self.left kushoto self.right hakidef maxPathSummizizi: TreeNode - int: def msaidizi mzizi: nonlocal maxSum ikiwa sio mizizi: kurudi 0 kushoto max0, msaidiziroot.left kulia max0, msaidiziroot.right maxSum maxmaxSum, kushoto kulia root.val return maxkushoto, kulia root.val maxSum kuelea-inf msaidizi mzizi kurudi maxSummaelezoAlgorithm inatokana na Utafutaji wa Kina wa Kwanza DFS wa mti wa binary.1. Unda kitendakazi cha usaidizi ambacho huchukua marejeleo ya jumla ya mzizi na upeo wa juu kama vigezo vya ingizo.2. Ikiwa nodi ya sasa mizizi ni batili, rudisha 0.3. Piga simu kitendakazi cha msaidizi kwa kujirudia kwa nodi za mtoto za kushoto na kulia: - Weka kushoto kama upeo wa 0 na simu ya kitendakazi cha msaidizi kwa mtoto wa kushoto. - Weka kulia kama upeo wa 0 na kitendakazi cha msaidizi kimwite mtoto anayefaa.4. Sasisha jumla ya njia ya juu kwa kutumia kiwango cha juu cha sasa, jumla ya thamani ya nodi ya sasa, na maadili ya watoto ya kushoto na kulia.5. Rejesha jumla ya thamani ya nodi ya sasa na upeo wa miti ndogo ya kushoto na kulia.Piga simu kitendakazi cha msaidizi na mzizi uliopewa wa mti wa binary na urudishe jumla ya njia ya juu zaidi. 