Construct Binary Tree from Preorder and Inorder Traversal
لديك مصفوفتان، preorder وinorder، تسردان القيم المميزة للشجرة الثنائية نفسها. يزور ترتيب سابق العقدة، ثم شجرتها الفرعية اليسرى، ثم شجرتها الفرعية اليمنى. ويزور الترتيب الوسطي الشجرة الفرعية اليسرى، ثم العقدة، ثم الشجرة الفرعية اليمنى.
أعِد بناء الشجرة وأرجِعها كمصفوفة بترتيب المستويات: الجذر عند الفهرس 0، وأبناء الفهرس i عند 2i+1 (الأيسر) و2i+2 (الأيمن)، وضع -1 في كل موضع فارغ. تنتهي المصفوفة عند آخر عقدة، من دون أي -1 زائدة في نهايتها.
الدالة
- preorderinteger-array
- القيم بترتيب الزيارة السابق: العقدة، الشجرة الفرعية اليسرى، الشجرة الفرعية اليمنى
- inorderinteger-array
- القيم بالترتيب الوسطي: الشجرة الفرعية اليسرى، العقدة، الشجرة الفرعية اليمنى
- تُرجعinteger-array
- الشجرة بترتيب المستويات، مع استخدام -1 للمواقع الفارغة ودون -1 في النهاية
القيود
1 ≤ preorder.length ≤ 3000inorder.length == preorder.length0 ≤ preorder[i] ≤ 104، وجميع القيم مميزة.inorderيحتوي على القيم نفسها، وتصف المصفوفتان الشجرة الثنائية نفسها.- عمق الشجرة لا يزيد عن
14، لذا فإن كل فهرس في الإجابة أقل من214-1 = 16383.
أمثلة
- المدخلات
- preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
- المخرجات
- [7, 3, 4, 0, 9, -1, 6]
- الشرح
- يبدأ الاجتياز السابق للترتيب من الجذر،
7. يقع عند الموضع3فيinorder، لذا تذهب0, 3, 9إلى اليسار، وتذهب4, 6إلى اليمين. ليس لدى4سوى ابن أيمن، وهو6، لذا يبقى الفهرس5عند-1.
- المدخلات
- preorder = [1, 2, 3]inorder = [2, 3, 1]
- المخرجات
- [1, 2, -1, -1, 3]
- الشرح
- يأتي الجذر
1أخيرًا فيinorder، لذا فإن الفهرس2هو-1. من بين2, 3، تضعpreorderالقيمة2أولًا، ويضعinorderالقيمة3بعدها، لذا فإن3هو ابنه الأيمن، عند الفهرس4.
سؤال إضافي
هل يمكنك إعادة بناء الشجرة دون استخدام الاستدعاء الذاتي، في مرور واحد على preorder باستخدام مكدس صريح؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
أي مصفوفة تخبرك بجذر الشجرة كلها، وأين يقع ذلك الجذر في المصفوفة الأخرى؟
تقسم العقدة الجذرية
inorderإلى قيم الشجرة الفرعية اليسرى وقيم الشجرة الفرعية اليمنى. فيpreorder، تأتي قيم الشجرة الفرعية اليسرى مباشرةً بعد العقدة الجذرية، وبالعدد نفسه الموجود في الجهة اليسرى. وينطبق التقسيم نفسه داخل كل شجرة فرعية.كرّر الاستدعاء على نطاق الترتيب الوسطي
lo..hiباستخدام فهرس الجذر في الترتيب السابق وفهرس الإخراجh: اكتب الجذر عندh، واعثر على موضعه في الترتيب الوسطيm، ثم أنشئ الجزء الأيسر عند2*h+1والجزء الأيمن عند2*h+2. تجعل الخريطة التي تربط القيمة بموضعها في الترتيب الوسطي العثور علىmيتم في خطوة واحدة.
الحل
يعطي الترتيب السابق جذر كل شجرة فرعية: أول قيمة في امتدادها. ويعطي الترتيب الوسطي موضع التقسيم: القيم التي تسبق الجذر تذهب إلى اليسار، والقيم التي تليه تذهب إلى اليمين. تؤدي إعادة تطبيق ذلك على النصفين إلى إعادة بناء الشجرة، وتتيح خريطة من القيمة إلى موضعها في الترتيب الوسطي العثور على موضع كل جذر بخطوة واحدة.
قسِّم تكراريًا، وابحث عن الجذر
الفكرة
في اجتياز سابق الترتيب، يأتي الفرع الفرعي الأيسر بعد جذره ويأخذ مدخلًا لكل قيمة، وعددها m-lo، حيث يمثل m موضع الجذر في اجتياز الترتيب الوسطي. يأتي الفرع الفرعي الأيمن بعده، لذا يقع جذره عند pre+1+(m-lo). في المثال الأول، يحتوي الجزء الأيسر 0, 3, 9 على ثلاث قيم، لذلك يبدأ الفرع الفرعي الأيمن عند فهرس اجتياز سابق الترتيب 4، أي عند القيمة 4.
يضمن عمق لا يتجاوز 14 أن يكون كل فهرس ناتج أقل من 2^14-1. املأ هذا العدد من الخانات بالقيمة -1، واكتب كل قيمة عند فهرسها، ثم احذف خانات -1 الزائدة في النهاية.
يستغرق مسح كل نطاق من نطاقات اجتياز الترتيب الوسطي بحثًا عن جذره O(n·h): لا تتداخل النطاقات في المستوى الواحد، لذا يمسح المستوى الواحد ما لا يزيد على n مدخلات، أي ما لا يزيد على 14 × 3000 = 42000 خطوة هنا. في غياب حد للعمق، تجعل شجرة على شكل مسار التعقيد O(n²).
الخوارزمية
- أنشئ
outمع2^14-1عنصرًا، جميعها-1. - اكتب
build(pre, lo, hi, h): إذا كانlo > hi، فأعِد. وإلا فاكتبpreorder[pre]فيout[h]. - امسح
inorderبدءًا منloللعثور على موضع الجذرm. يحتوي الفرع الأيسر علىm-loقيمة. - استدعِ
build(pre+1, lo, m-1, 2*h+1)وbuild(pre+1+(m-lo), m+1, hi, 2*h+2). - استدعِ
build(0, 0, n-1, 0)، ثم احذف عناصر-1الزائدة في النهاية وأعِد الباقي.
def buildTree(preorder, inorder):
out = [-1] * (2 ** 14 - 1) # every index of a depth-14 tree is below 2^14-1
def build(pre, lo, hi, h):
# preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
# it goes to index h of the output.
if lo > hi:
return
value = preorder[pre]
out[h] = value
m = lo
while inorder[m] != value: # find the root in the inorder range
m += 1
left_size = m - lo
build(pre + 1, lo, m - 1, 2 * h + 1)
build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)
build(0, 0, len(inorder) - 1, 0)
last = len(out) - 1
while out[last] == -1: # trim the trailing -1 entries
last -= 1
return out[:last + 1]قسّم تكراريًا باستخدام خريطة مواضع
الفكرة
القيم متميزة، لذا لكل منها موضع واحد بالضبط في inorder. سجّل هذا الموضع في خريطة تربط القيمة بالموضع قبل بدء الاستدعاء التكراري، وعندها يستغرق كل بحث عن الجذر خطوة واحدة.
يستغرق إنشاء الخريطة O(n)، ثم توضع كل قيمة مرة واحدة بعمل ثابت، لذا يكون الزمن الإجمالي O(n). تشغل الخريطة مساحة O(n)، ويستهلك الاستدعاء التكراري إطارًا واحدًا لكل مستوى. في C وR، لا تتجاوز القيم 10^4، لذا تصلح مصفوفة عادية من 10^4+1 مدخلًا لتكون الخريطة.
الخوارزمية
- أنشئ خريطة تربط كل قيمة في
inorderبموضعها. - أنشئ
outمع2^14-1مدخلًا، جميعها-1. - في
build(pre, lo, hi, h)، أَعِد إذا كانlo > hi؛ وإلا فاكتبpreorder[pre]فيout[h]وابحث عن موضعهاmفي الخريطة. - استدعِ تكراريًا
build(pre+1, lo, m-1, 2*h+1)وbuild(pre+1+(m-lo), m+1, hi, 2*h+2). - استدعِ
build(0, 0, n-1, 0)، ثم احذف مدخلات-1في النهاية وأعِد الباقي.
def buildTree(preorder, inorder):
position = {value: i for i, value in enumerate(inorder)} # value -> inorder index
out = [-1] * (2 ** 14 - 1) # every index of a depth-14 tree is below 2^14-1
def build(pre, lo, hi, h):
# preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
# it goes to index h of the output.
if lo > hi:
return
value = preorder[pre]
out[h] = value
m = position[value]
left_size = m - lo
build(pre + 1, lo, m - 1, 2 * h + 1)
build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)
build(0, 0, len(inorder) - 1, 0)
last = len(out) - 1
while out[last] == -1: # trim the trailing -1 entries
last -= 1
return out[:last + 1]
أخطاء شائعة وحالات حدّية
- بدء الشجرة الفرعية اليمنى عند
pre+1+mبدلًا منpre+1+(m-lo). ينجح ذلك عندما تكونloتساوي0، كما في الاستدعاء الأول، ويتعطل عندما يبدأ نطاق من موضع لاحق. - إسقاط الخانات الفارغة. تظل خانة الابن المفقود محجوزة، لذا تكون إجابة المثال الثاني
[1, 2, -1, -1, 3]، وليس[1, 2, 3]. - ترك خانات
-1زائدة في النهاية. إرجاع جميع الخانات البالغ عددها2^14-1يجعل في المثال الأول 16376 خانة-1إضافية. - نسخ أجزاء من المصفوفتين عند كل استدعاء، ما يضيف
O(n)في كل مستوى. مرّر نطاقات الفهارس. - في Lua وR، تبدأ المصفوفات من 1. أبقِ المواضع معدودة من 0 للحسابات، واقرأ
preorder[pre + 1]وout[h + 1].
أسئلة شائعة3
لماذا تحتاج إلى كلٍّ من الترتيب السابق والترتيب الوسطي لإعادة بناء شجرة ثنائية؟
لا يحدد الترتيب السابق للشجرة شكلها بمفرده. فالترتيب السابق [1, 2] يناسب شجرة تكون فيها 2 الابن الأيسر لـ 1، كما يناسب شجرة تكون فيها الابن الأيمن. يحسم الترتيب الوسطي الأمر: [2, 1] يضع 2 على اليسار، و[1, 2] يضعه على اليمين. عندما تكون القيم مميزة، يصف الزوج شجرة واحدة بالضبط.
ما هو التعقيد الزمني لبناء شجرة ثنائية من اجتيازَي الترتيب السابق والترتيب الداخلي؟
باستخدام خريطة تربط كل قيمة بموضعها في الترتيب الوسطي، يكون التعقيد الزمني O(n) والمساحة الإضافية O(n). ومن دون الخريطة، فإن البحث في كل نطاق من الترتيب الوسطي عن الجذر يستغرق O(n·h)، ويصبح O(n²) في شجرة يتخذ شكلها هيئة مسار.
هل يمكنك إعادة بناء شجرة ثنائية من اجتيازَي الترتيب المسبق والترتيب اللاحق؟
ليس بشكل عام. يتوافق الترتيب السابق [1, 2] والترتيب اللاحق [2, 1] مع كلٍّ من الابن الأيسر والابن الأيمن، لأن أياً من طريقتَي الاجتياز لا تضع الجذر بين أشجاره الفرعية. يكفي هذا الزوج فقط لشجرة ثنائية ممتلئة، حيث يكون لكل عقدة صفر أو ابنان.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def buildTree(preorder, inorder):
# اكتب الكود هنااختبار #1
اختبار #2
الوسائط
preorder = [7, 3, 0, 9, 4, 6] inorder = [0, 3, 9, 7, 4, 6]
الإخراج المتوقع
[7, 3, 4, 0, 9, -1, 6]