نتاج جميع العقد باستثناء واحد في شجرة ثنائية

Question

افترض أننا حصلنا على شجرة ثنائية مع عدد صحيح يجلس في كل عقدة.أنا أبحث عن طريقة فعالة للعثور على كل مسار من الجذر إلى ورقة كل منتج ممكن مع عقدة واحدة بالضبط حذفت.أبحث عن حل بدون أقسام (I.E. الأعداد الصحيحة يمكن أن يكون صفر).

طريقة واحدة للذهاب حول هذا فكرت في يمكنني حساب جميع المنتجات الجزئية الممكنة بدءا من الجذر.هذه هي كل عقدة تخزن نتاج المسار الفريد من الجذر حتى هذه العقدة (ولكن باستثناء عدد صحيح مخزن في تلك القيمة الخاصة).ثم لكل عقدة ورقة يمكنني سرور المسار إلى عقدة الجذر مضاعفة الأعداد الصحيحة في الطريق.في عقدة معينة قبل تتراكم العقدة في المنتج، يمكنني ضرب المنتج مع منتج البادئة المخزنة في العقدة.

يشعر وكأنني أفعل الكثير من الضربات الزائدة عند زيارة كل مسار من ورقة إلى الجذر، لأن هذه المسارات يحتمل أن تشارك الكثير من العقد.هل هناك طريقة أسرع للقيام بذلك؟

Answer 1

نهج بسيط واحد: للحصول على عقدة داخلية $ x $ ، دع $ p (x) $ تدل على نتاج الأعداد الصحيحة على المسار من الجذر إلى $ x $ ، واسمحوا $ Q (x) $ < / span> تدل على مجموعة من الأعداد الصحيحة التي يمكن الحصول عليها كمنتج لجميع الأعداد الصحيحة ولكن أحد الأعداد الصحيحة على الطريق من الجذر إلى $ x $ . الآن، ينزل الشجرة من الجذر وصولا إلى الأوراق، والحوسبة $ p (x) $ و $ q (x) $ لكل عقدة $ x $ كما تذهب. لاحظ أنه يمكنك حساب $ p (x)، q (x) $ من $ p (w)، q (w)، q (w ) $ ، حيث $ W $ هو أصل $ x $ .

ستكون وقت التشغيل الأسوأ للقهر $ O (n ^ 2) $ . لا توجد خوارزمية أفضل وقت تشغيل مقارب الحالة، حيث يمكن أن يكون هناك $ \ theta (n ^ 2) $ منتجات مختلفة تحتاج إلى الإخراج، لذلك أي خوارزمية صحيحة ستحتاج إلى أن يكون لديك وقت تشغيل الأسوأ على الأقل $ \ theta (n ^ 2) $ .