عنوان:
مجموع المسار الشجرة الثنائية
بالنظر إلى شجرة ثنائية ، ابحث عن مبلغ المسار القصوى.
قد يبدأ المسار وينتهي في أي عقدة في الشجرة.
على سبيل المثال:
بالنظر إلى الشجرة الثنائية أدناه ،
1 / / 2 3
العودة 6.
قد تكون العقدة سالبة ، وتبحث عن المسار الأكثر بحيرة بحيث تكون العقد التي تمر بها هي الأكبر. يمكن أن يبدأ المسار وينتهي في أي عقدة ولكن لا يمكن العودة.
على الرغم من أن هذا السؤال يبدو غير عادي ، إذا فكرت في الأمر ، ستجد أنه ليس أكثر من اجتياز الأشجار الثنائية + أفكار التخطيط الديناميكية البسيطة.
يمكننا فصل المشكلة: حتى لو لم يمر آخر مسار عبر عقدة الجذر ، فيجب أن يكون له "أعلى نقطة". لذلك ، نحتاج فقط إلى معرفة جميع العقد: إذا كان المسار يأخذ هذه العقدة باعتبارها "أعلى نقطة" ، فما هو الحد الأقصى لطول المسار؟ لاحظ كحد أقصى. ثم ابحث عن الحد الأقصى لقيمة الحد الأقصى في الحد الأقصى ، وهي النتيجة التي تبحث عنها. نفس الفكرة مثل "العثور على أكبر فترة مستمرة في تسلسل عدد صحيح".
فيما يلي العثور على العلاقة بين الحد الأقصى المقابل لكل "أعلى نقطة".
لنأخذ عقدة الجذر كمثال. طريقة الحساب للمسار الأقصى الذي يمر عبر عقدة الجذر هي:
نجد الحد الأقصى لطول المسار A في الشجرة الفرعية اليسرى مع الطفل الأيسر كنقطة انطلاق ، وطول المسار الأقصى B في الشجرة الفرعية اليمنى مع الطفل الأيمن كنقطة انطلاق. ثم الحد الأقصى = بحد أقصى لهذه النقطة (A+B+Node.val ، A+Node.val ، B+Node.val ، Node.val)
لذلك ، نحدد وظيفة لحساب A أو B أعلاه. معلمةها هي عقدة ، وقيمة إرجاعها هي الحد الأقصى لطول المسار. ومع ذلك ، يجب أن تكون نقطة انطلاق هذا المسار هي عقدة الإدخال ، ويجب أن يكون المسار على شجرة فرعية مع نقطة البداية مثل عقدة الجذر.
ثم يمكن تعريف قيمة الإرجاع للدالة func (العقدة) على النحو التالي: returnmax (func (node.left)+node.val ، func (node.right)+node.val ، node.val)
حالة الإنهاء هي العقدة == فارغة ، وتعود 0 مباشرة.
ثم وجدنا أن العملية أعلاه لحساب Max وحساب Max يمكن وضعها بالكامل في Func (العقدة).
وفقًا لرمز هذه الفكرة ، فإن MaxPathsumCore هو التنفيذ أعلاه لـ FUNC (العقدة):
/** * تعريف للشجرة الثنائية * هيكل treenode { * int val ؛ * treenode * اليسار ؛ * treenode * الحق ؛ * treenode (int x): val (x) ، left (null) ، right (null) {} *} ؛ */Class Solution {public: int maxpathsum (treenode *root) {maxpathsumcore (root) ؛ return max ؛} int maxpathsumcore (treenode *node) {if (null == node) return 0 ؛ int a = maxpathsumcore (node -> int b = maxpathsumcore (node -> يمين) ؛ if ((A+B+Node-> val)> max) max = (a+b+node-> val) ؛ if ((a+node-> val)> max) max = (a+node-> val) ؛ if (b+node-> val)> max) max = b+node-> val) ؛ maxviathisnode = ((a + node-> val)> node-> val؟ (a + node-> val): node-> val) ؛ return (maxviathisnode> (b + node-> val)؟ maxviathisnode: (b + node-> val)) ؛تعقيد الوقت O (N) ، N هو العدد الإجمالي للعقد.
لخص
ما سبق هو المحتوى الكامل لهذه المقالة حول تحليل رمز المسار الأقصى للشجرة الثنائية في برمجة Java. آمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى الموضوعات الأخرى ذات الصلة على هذا الموقع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها. شكرا لك يا أصدقائك لدعمكم لهذا الموقع!