لطفا توضیح بدید
یک درخت دودوییt با nگره داده شده.میخواهیم زیر درخت پر t را بدست اوریم..مرتبه بهترین الگوریتم برای محاسبه زیر درخت پر tبا بیشترین تعداد عناصر؟؟؟
یه روال کلی اینطور هست که از به برگا که رسیدیم، این برگا خودشون فکر کنم یه زیر درخت پر هستن با سایز ۱! حالا از این برگا که بریم بالا اگه پدرشون هر دوتا بچش رو داشت سایز پدر میشه سایز زیر درخت پر به ریشه بچه هاش به علاوه خودش و ... یه حالت داینامیک داره و اگه شما مثلا یه الگوریتم مثل DFS رو از ریشه شروع کنی به جواب نهایی برسی که مرتبش از n میشه.
البته اینا ممکنه اشتباه باشن
همونطور که هادی گفت با dfs حل میشه
اینجوری عمل می کنیم اگر به برگ رسیدیم یک بر می گردونیم
اول فرزند چپ را صدا می زنیم بعد فرزند راست هر کدام عددی بر می گردانند اگر با هم برابر بودن این دو عدد را جمع و با max مقایسه می کنیم اگر بزرگتر بود این نود را همراه با عددش در ماکس ذخیره می کنیم
این عدد بدست آمده را به عنوان مقدار بازگشتی به پدر می دهیم
اگر این دو عدد برابر نباشند صفر برمی گردانیم
مرتبه میشه n اگه اشتباه نکنم