Aller au contenu

Arbre-somme

🏷️ On considère ici des arbres étiquetés par des nombres.

Arbre-somme

Pour les besoins de cet exercice, on dira qu'un arbre est un arbre-somme si tout nœud, sauf si c'est une feuille, porte une étiquette égale à la somme des étiquettes de ses sous-arbres.

Exemple

graph TB
    R(19)
    R --- Rg(3)
    R --- Rm(4)
    R --- Rd(5)
    Rg --- Sg(1)
    Rg --- Sd(2)
    Rm --- T(4)

Pas de proposition naïve

⚠ Une proposition qui consiste à recalculer entièrement la somme de tous les sous-arbres pour chaque nœud qui n'est pas une feuille ne sera pas acceptée ; trop lente !

👍 On attend une proposition avec un parcours unique de l'arbre qui pourra avoir près d'un million de nœuds.

Exercice

Coder une fonction est_arbre_somme qui prend arbre en paramètre et qui renvoie un booléen :

  • True si arbre est un arbre-somme,
  • False sinon.

On garantit que chaque étiquette est un entier Python.

👍 On garantit que la hauteur de l'arbre est inférieure à mille ; pour éviter les erreurs avec un code récursif. 😉

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞
.128013,59/fT78rnb _o=ylaepcwgu)*vd46F13kRméhtsP(S0+2-i:050C0t0N0s0W0r0O0m0v0r0s0O0O0p010N0W0u010406050O0y0K0K0s0j0q040R0o0r0y0=0o0k050e0|0~10120`0u04051i1b1l0e1i0`0C0W0B0*0,0.0:0M0W0x0M0r1z0M0N0^050#0l0r0t1u0-0/011y1A1C1A0N1I1K1G0N0j1j0N0M1M1w010f0%0t0k0s0K0t010*150O0u0s0k0:0U1G1@1_1%1O1*1K1-1/0^0a0m0P0j0o0u0o0O0W180k0m0Z1=0j0j0t0v2g1b1~0k1j0e1#2t1Y1!1Z1H0C200:1C0k1,2d1G1r1t0+1N2D0W2F0k0o2J1G0u2m1j2r2t2X0{1^2h2L1(2Q0j0 0r0^0m0G2q2#0_2!1 2%1O2)2+2-0U2:1_2=2r2C012`0s2,040m0H2~2s0`312^0:34360m0D3a302#323g2-0c3k3c3m3e330o2*352-0E3r2?2$1v2_3w2{370h3B3d3E3f3G3y370i3K3t3M3v3x3h0d3S2@3U3o040G0S3Z3D2M3V3H0G2/1c2;3s3!3,3$0G2}3;2 3?3+2(3O360G393|3b3C3n410^0G3j453l3@403W4a3q4d1m2V1b2J2w0C1!2B3u0v2R1:1j4o1k4m2Z4k4u0Z2W3T3,0I0^0Z0f3k473u0w2-4M3L3^0f0^0t0O0N0n100l2m0n0O0o0~0t4R4G1(0@040Q4,4f2_0^4!2m4=3 1O4/0z0X3r0m520m4N3U0O1|04010J1,0B0o0W1L0y2h0l0o150L1,0m0X0m0g0j0y1L2e0m4_1L4W0N0m5h5w0j4#0t0V4(4*0b0m0F350O5u2O19015153553^0^0j0s0v2O4+4k4S4.0^0b3k545(4@041,0f1_0N0O5,5V1(0o0^0p5_5.3f4^5E4`4d06535-4-1O4I040W4L4d684?3f0l0^234{324/4;5%69615:0k5=0k5@6m3u4~5 6r015|040p5~6f5`1O0K0W0^3)6q6h014/506567676J0:6b2m0N0y0j1a6I60010I0v0^5r5t5T526X330^5I1/6B6Q6E6H2X6g4|0:6L6N6;70326b0f3w6{716@6t6v0N7b320o4P6c6(6 6?0k4V6u5?5^6P7c6S756W6*6b6d7h3u7j0^2Q7g6)6C7p5:4X4Z630t4%4)6`7u6n0^6p2Z6*7K5;5?6y3U4~6T2X666V7,6?6Z0!6$7m2;763u6,0^5M0(5$7*7,6=7Y5X5Z5#0n7!6w7$3,4/5+7I6Q7K0u0!2f0O857r6w7t7n6*6}7C3#7q7f7x5U7z0^7B8c7c0k6j046l7T6z7V882(0^8f0=5@8j7f8m2;6?6A8z7i5}6~7?6?73046O7X6C7w6U7 7y7J6^7R7}8Y8o0^0T8X2 7@8r045Y5!2F8O7#8*7-8w5:7|8I4}0^7)3=8+8,8d8.4*8q3,6E8@9h1(8!3{8n6C6E0A9l5/8}84867H7~8v6C7/6#6%9t6s6_8:8_6?6}8^2s8`5W8|832F3B0e4D0t2t2U9W4n1s4p2w2z2u0s1J9Z0e4o0`9-0!0$0(04.