Arbre de sumes parelles X24006

Statement

html

Implementeu una funció RECURSIVA que, donat un arbre binari d’enters, retorna un nou arbre amb la mateixa estructura, i a on cada posició a profunditat parella conté la suma de nodes del subarbre que penja d’aquella mateixa posició a l’arbre inicial. Aquesta és la capcelera:

// Pre:
// Post: Retorna un arbre d'enters amb la mateixa estructura que t,
//       i a on cada subarbre a profunditat parella té com a arrel la suma dels nodes del corresponent subarbre a t.
BinaryTree<int> pairtreeOfSums(BinaryTree<int> t);

L’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: Makefile, program.cpp, BinaryTree.hpp, pairtreeOfSums.hpp. Us falta crear el fitxer treeOfSums.cpp amb els corresponents includes i implementar-hi la funció anterior. Quan pugeu la vostra solució al jutge, només cal que pugeu aquest fitxer:

tar cf solution.tar pairtreeOfSums.cpp

Entrada

L’entrada té un nombre arbitrari de casos. Cada cas consisteix en una línia amb un string describint un arbre binari d’enters. Fixeu-vos en que el programa que us oferim ja s’encarrega de llegir aquestes entrades. Només cal que implementeu la funció abans esmentada.

Sortida

Per a cada cas, la sortida conté el corresponent arbre de sumes a alçada parella. Fixeu-vos en que el programa que us oferim ja s’encarrega d’escriure aquesta sortida. Només cal que implementeu la funció abans esmentada.

Public test cases

Input

8(4(6,3(2,1)),5)
1(1(1,1),1(1,1))
2(4(7(5,3),1(3,3)),2(8,7(2(7,9),2)))
3(7(5,0),3(5,0))
6(1,2)
6(,5(7,2))
5
4(6(1,3),)
4(,8(8(1,5),4(7,)))
4

Output

17(4(6,6(2,1)),5)
3(1(1,1),1(1,1))
8(4(15(5,3),7(3,3)),2(8,11(2(7,9),2)))
13(7(5,0),3(5,0))
9(1,2)
11(,5(7,2))
5
10(6(1,3),)
12(,8(14(1,5),11(7,)))
4

Input

0(55(29(-47(-15,98),),-18(86(-59(60(29(,-38),30),-13(-80,-29)),62(-21,2(12(-28,-20),-67(-58,-79)))),-56(-5(-100(-37(7,-70),-18(,-82)),-34(30,94(-46,))),96(,51(63(41,-88),))))),-8)
75(-46(-53(-48,-53),98(,61)),-49)
67(25,-50)
9(-87,25(95,))
15(-92(-47(70,),-87),)
4(-1(27,-35),)
78(86(-5(,68),),46(88(-59,-9(68,83)),79(89(-93,-72),-31(-76,-91))))
-25(93(76(4,-8),-51(-22(-3,21),31(-34,32))),-95(-40(,53),93(,-81(16(-61,13(89,)),-7(-20,37)))))
94(37(,6),72(-90(,24(,-38(55(-65,22),46))),38(69(22(-65,-12),-54(49(78,-10),-3)),52(56,39(80(,24(-48,)),8(68(-38(,85),27(76,-13)),33(74,32)))))))
58
-20(82,81(-19,37))
97(-45(53(87(-96(-16(-35,97(,-23)),65(97,52(56,))),59(20(55(77,-30),),61)),),-26(98(,15),48(,-71(-22,)))),90(-99(88(,-4(-79(52(-16,),-27(,-80)),-36(-94,83))),),57(25(66(42(-49(-6,26),),57(-96,-75)),96(-15(,-46(,27)),1(91,44))),40(,-44))))
-6(-10(,25(80,6(57,47))),-60(80,87))
40(-71(4(-17(90(,-4(,-57)),-67(,-87)),100),20(14(-28,80),-11(-30,-2))),70(80,))
-14(-95(-31(41(-30(59(-71(27,-4),-75(,-92)),),59),-42),13(31(,-79),-24(62(52(80,-94(,-60)),26(,39)),8(45(,53),-73(11,26))))),60(-2(-2(-73,78(-82,10(-71(,-45(-19,-16)),-28))),-96(-12(88(83(-6,-52(7,-29)),-80),-39(33(11(,35),12),36(11(,13(53(-94,),-67)),30(-4,57)))),41(,66(91,97)))),-64(,93(49,))))
8(54(11(-99(67(7,),),-47(-10,-18)),82(9,-9)),43(16,-56))
-69(-15(25(57(38(-54,-13),80),-5),39(,-5(-28(-34,),74(-30,)))),67(41(4,),-19(72,)))
-53(19,35(9(29(-5,87),-60(21(-7,-16),)),62(-37(90(47,28),-35(91,40)),60)))
40(-49(-36,-47(51(-22(-7(-67(74(33,-100),18),-91(13,)),-69(73(-3,53(5,-65)),)),74(-100,-88)),42(-69(-100,),-35(27(28(-70(40(48,),-46(-26(-40,),)),14(,13)),-51(7,-40)),40(-53(0(57,83),7(-47(18,55),18(-58,))),-48))))),97(88(69(-81(,-9(49(21(33(67(61,-38),),-74),77(22(28,-43(-93,88)),-43(55(-73,-25),))),)),55(-52,)),-38(100(79(3,42(-63(,41(,-1)),50)),-90(0(-40(-11,-93(99,)),28(-95(-55,),-28)),)),-38(,-61(-71(40(,-71),),-66(12(-33,-73),))))),18(-8(100(-98(,1(-28(70(35(7,-25),-61),),99)),13(83(19(-91,-38),76(27,-79)),55)),49(-86(-58(60,8),-34),17(-27(52(82,),-22(-15,)),-99(31(-28(98,-23),-55(59(93,),)),-65(-15(5(28,-79),95(60,93)),-82(-91(20,),-1(61,))))))),-53(69(82,),4(-50(,-55(90(-86,-51),-72(-97(5(55,),),))),0(-31(57(22(-94,),48(-71(,57),-93(3,))),-63(-79(96,-20),-18(-27,-99))),29(51,38(70,))))))))
-9(-64(16,),49(-79,74))

Output

47(55(-18(-47(-15,98),),12(86(-12(60(-9(,-38),30),-13(-80,-29)),43(-21,2(-36(-28,-20),-204(-58,-79)))),-56(-139(-100(-100(7,-70),-100(,-82)),-34(30,48(-46,))),147(,51(16(41,-88),))))),-8)
-20(-46(-154(-48,-53),159(,61)),-49)
42(25,-50)
-53(-87,25(95,))
-77(-92(23(70,),-87),)
3(-1(27,-35),)
210(86(63(,68),),46(20(-59,-9(68,83)),137(89(-93,-72),-31(-76,-91))))
-27(93(72(4,-8),-42(-22(-3,21),31(-34,32))),-95(13(,53),12(,-81(-32(-61,13(89,)),10(-20,37)))))
203(37(,6),72(-66(,24(,63(55(-65,22),46))),159(69(-55(-65,-12),-8(49(78,-10),-3)),52(56,127(80(,-24(-48,)),8(57(-38(,85),27(76,-13)),139(74,32)))))))
58
143(82,81(-19,37))
142(-45(140(87(-47(-16(-35,74(,-23)),65(97,108(56,))),140(20(102(77,-30),),61)),),120(98(,15),48(,-93(-22,)))),90(-11(88(,-119(-79(36(-16,),-107(,-80)),-36(-94,83))),),122(25(165(42(-29(-6,26),),57(-96,-75)),82(-15(,-19(,27)),1(91,44))),40(,-44))))
-76(-10(,111(80,6(57,47))),-60(80,87))
39(-71(87(-17(86(,-4(,-57)),-154(,-87)),100),23(14(-28,80),-11(-30,-2))),70(80,))
-49(-95(-32(41(29(59(-48(27,-4),-167(,-92)),),59),-42),20(31(,-79),-24(140(52(80,-154(,-60)),26(,39)),-20(45(,53),-73(11,26))))),60(-100(-2(-73,6(-82,10(-116(,-45(-19,-16)),-28))),-96(37(88(25(-6,-52(7,-29)),-80),-39(56(11(,35),12),77(11(,-1(53(-94,),-67)),30(-4,57)))),107(,66(91,97)))),29(,93(49,))))
105(54(-135(-99(74(7,),),-47(-10,-18)),82(9,-9)),43(16,-56))
-17(-15(77(57(-29(-54,-13),80),-5),34(,-5(-62(-34,),44(-30,)))),67(45(4,),53(72,)))
1(19,35(-22(29(-5,87),-60(-2(-7,-16),)),85(-37(165(47,28),96(91,40)),60)))
88(-49(-36,46(51(-98(-7(25(74(33,-100),18),-78(13,)),-69(123(-3,53(5,-65)),)),-114(-100,-88)),42(-169(-100,),32(27(-28(-70(88(48,),-72(-26(-40,),)),14(,13)),-84(7,-40)),40(-46(0(57,83),7(26(18,55),-40(-58,))),-48))))),97(119(69(-90(,-9(147(21(100(67(61,-38),),-74),77(7(28,-43(-93,88)),12(55(-73,-25),))),)),3(-52,)),-38(89(79(3,29(-63(,40(,-1)),50)),-90(-12(-40(-11,6(99,)),28(-150(-55,),-28)),)),-99(,-61(-31(40(,-71),),-54(12(-33,-73),))))),-43(-8(15(-98(,72(-28(44(35(7,-25),-61),),99)),13(178(19(-91,-38),76(27,-79)),55)),-20(-86(10(60,8),-34),17(3(52(82,),-22(-15,)),-133(31(47(98,-23),4(59(93,),)),-65(85(5(28,-79),95(60,93)),-174(-91(20,),-1(61,))))))),-53(151(82,),-46(-50(,-37(90(-86,-51),-72(-92(5(55,),),))),0(-37(57(-72(-94,),-116(-71(,57),-93(3,))),-63(-3(96,-20),-144(-27,-99))),118(51,38(70,))))))))
-24(-64(16,),49(-79,74))

Input

0(55(29(-47(-15,98),),-18(86(-59(60(29(,-38),30),-13(-80,-29)),62(-21,2(12(-28,-20),-67(-58,-79)))),-56(-5(-100(-37(7,-70),-18(,-82)),-34(30,94(-46,))),96(,51(63(41,-88),))))),-8)
75(-46(-53(-48,-53),98(,61)),-49)
67(25,-50)
9(-87,25(95,))
15(-92(-47(70,),-87),)
4(-1(27,-35),)
78(86(-5(,68),),46(88(-59,-9(68,83)),79(89(-93,-72),-31(-76,-91))))
-25(93(76(4,-8),-51(-22(-3,21),31(-34,32))),-95(-40(,53),93(,-81(16(-61,13(89,)),-7(-20,37)))))
94(37(,6),72(-90(,24(,-38(55(-65,22),46))),38(69(22(-65,-12),-54(49(78,-10),-3)),52(56,39(80(,24(-48,)),8(68(-38(,85),27(76,-13)),33(74,32)))))))
58
-20(82,81(-19,37))
97(-45(53(87(-96(-16(-35,97(,-23)),65(97,52(56,))),59(20(55(77,-30),),61)),),-26(98(,15),48(,-71(-22,)))),90(-99(88(,-4(-79(52(-16,),-27(,-80)),-36(-94,83))),),57(25(66(42(-49(-6,26),),57(-96,-75)),96(-15(,-46(,27)),1(91,44))),40(,-44))))
-6(-10(,25(80,6(57,47))),-60(80,87))
40(-71(4(-17(90(,-4(,-57)),-67(,-87)),100),20(14(-28,80),-11(-30,-2))),70(80,))
-14(-95(-31(41(-30(59(-71(27,-4),-75(,-92)),),59),-42),13(31(,-79),-24(62(52(80,-94(,-60)),26(,39)),8(45(,53),-73(11,26))))),60(-2(-2(-73,78(-82,10(-71(,-45(-19,-16)),-28))),-96(-12(88(83(-6,-52(7,-29)),-80),-39(33(11(,35),12),36(11(,13(53(-94,),-67)),30(-4,57)))),41(,66(91,97)))),-64(,93(49,))))
8(54(11(-99(67(7,),),-47(-10,-18)),82(9,-9)),43(16,-56))
-69(-15(25(57(38(-54,-13),80),-5),39(,-5(-28(-34,),74(-30,)))),67(41(4,),-19(72,)))
-53(19,35(9(29(-5,87),-60(21(-7,-16),)),62(-37(90(47,28),-35(91,40)),60)))
40(-49(-36,-47(51(-22(-7(-67(74(33,-100),18),-91(13,)),-69(73(-3,53(5,-65)),)),74(-100,-88)),42(-69(-100,),-35(27(28(-70(40(48,),-46(-26(-40,),)),14(,13)),-51(7,-40)),40(-53(0(57,83),7(-47(18,55),18(-58,))),-48))))),97(88(69(-81(,-9(49(21(33(67(61,-38),),-74),77(22(28,-43(-93,88)),-43(55(-73,-25),))),)),55(-52,)),-38(100(79(3,42(-63(,41(,-1)),50)),-90(0(-40(-11,-93(99,)),28(-95(-55,),-28)),)),-38(,-61(-71(40(,-71),),-66(12(-33,-73),))))),18(-8(100(-98(,1(-28(70(35(7,-25),-61),),99)),13(83(19(-91,-38),76(27,-79)),55)),49(-86(-58(60,8),-34),17(-27(52(82,),-22(-15,)),-99(31(-28(98,-23),-55(59(93,),)),-65(-15(5(28,-79),95(60,93)),-82(-91(20,),-1(61,))))))),-53(69(82,),4(-50(,-55(90(-86,-51),-72(-97(5(55,),),))),0(-31(57(22(-94,),48(-71(,57),-93(3,))),-63(-79(96,-20),-18(-27,-99))),29(51,38(70,))))))))
-9(-64(16,),49(-79,74))

Output

47(55(-18(-47(-15,98),),12(86(-12(60(-9(,-38),30),-13(-80,-29)),43(-21,2(-36(-28,-20),-204(-58,-79)))),-56(-139(-100(-100(7,-70),-100(,-82)),-34(30,48(-46,))),147(,51(16(41,-88),))))),-8)
-20(-46(-154(-48,-53),159(,61)),-49)
42(25,-50)
-53(-87,25(95,))
-77(-92(23(70,),-87),)
3(-1(27,-35),)
210(86(63(,68),),46(20(-59,-9(68,83)),137(89(-93,-72),-31(-76,-91))))
-27(93(72(4,-8),-42(-22(-3,21),31(-34,32))),-95(13(,53),12(,-81(-32(-61,13(89,)),10(-20,37)))))
203(37(,6),72(-66(,24(,63(55(-65,22),46))),159(69(-55(-65,-12),-8(49(78,-10),-3)),52(56,127(80(,-24(-48,)),8(57(-38(,85),27(76,-13)),139(74,32)))))))
58
143(82,81(-19,37))
142(-45(140(87(-47(-16(-35,74(,-23)),65(97,108(56,))),140(20(102(77,-30),),61)),),120(98(,15),48(,-93(-22,)))),90(-11(88(,-119(-79(36(-16,),-107(,-80)),-36(-94,83))),),122(25(165(42(-29(-6,26),),57(-96,-75)),82(-15(,-19(,27)),1(91,44))),40(,-44))))
-76(-10(,111(80,6(57,47))),-60(80,87))
39(-71(87(-17(86(,-4(,-57)),-154(,-87)),100),23(14(-28,80),-11(-30,-2))),70(80,))
-49(-95(-32(41(29(59(-48(27,-4),-167(,-92)),),59),-42),20(31(,-79),-24(140(52(80,-154(,-60)),26(,39)),-20(45(,53),-73(11,26))))),60(-100(-2(-73,6(-82,10(-116(,-45(-19,-16)),-28))),-96(37(88(25(-6,-52(7,-29)),-80),-39(56(11(,35),12),77(11(,-1(53(-94,),-67)),30(-4,57)))),107(,66(91,97)))),29(,93(49,))))
105(54(-135(-99(74(7,),),-47(-10,-18)),82(9,-9)),43(16,-56))
-17(-15(77(57(-29(-54,-13),80),-5),34(,-5(-62(-34,),44(-30,)))),67(45(4,),53(72,)))
1(19,35(-22(29(-5,87),-60(-2(-7,-16),)),85(-37(165(47,28),96(91,40)),60)))
88(-49(-36,46(51(-98(-7(25(74(33,-100),18),-78(13,)),-69(123(-3,53(5,-65)),)),-114(-100,-88)),42(-169(-100,),32(27(-28(-70(88(48,),-72(-26(-40,),)),14(,13)),-84(7,-40)),40(-46(0(57,83),7(26(18,55),-40(-58,))),-48))))),97(119(69(-90(,-9(147(21(100(67(61,-38),),-74),77(7(28,-43(-93,88)),12(55(-73,-25),))),)),3(-52,)),-38(89(79(3,29(-63(,40(,-1)),50)),-90(-12(-40(-11,6(99,)),28(-150(-55,),-28)),)),-99(,-61(-31(40(,-71),),-54(12(-33,-73),))))),-43(-8(15(-98(,72(-28(44(35(7,-25),-61),),99)),13(178(19(-91,-38),76(27,-79)),55)),-20(-86(10(60,8),-34),17(3(52(82,),-22(-15,)),-133(31(47(98,-23),4(59(93,),)),-65(85(5(28,-79),95(60,93)),-174(-91(20,),-1(61,))))))),-53(151(82,),-46(-50(,-37(90(-86,-51),-72(-92(5(55,),),))),0(-37(57(-72(-94,),-116(-71(,57),-93(3,))),-63(-3(96,-20),-144(-27,-99))),118(51,38(70,))))))))
-24(-64(16,),49(-79,74))

Information

Author: STUDENTS PRO1
Language: Catalan
Official solutions: Make
User solutions: Make