DOM Challenge – شماره 1

من قصد دارم حدود 30 پست را بنویسم که شامل سؤالات مختلف مربوط به Traversal ، دستکاری و بهینه سازی DOM است.

سوال امروز مربوط به Dom Traversal است

سوال:
اجداد مشترک دو عنصر DOM داده شده را پیدا کنید.

در این سؤال ما درخت DOM داریم و باید اجداد مشترک گره های داده شده را پیدا کنیم. اولین رویکردی که می توانم به آن فکر کنم جمع آوری تمام گره های والدین هر دو عنصر و یافتن اولین گره مشترک است.

ما می توانیم با استفاده از این روش ، والدین را بدست آوریم

const parentList = (element)=>{
    let el = element;
   const list = [];
    while(true){
        list.push(el);

        if(!el.parentNode) break;
        el = el.parentNode;
    }

    return list;
}

اکنون می توانیم از این لیست برای یافتن LCA استفاده کنیم –

const findLCA = (el1, el2)=>{
    const parentList1 = parentList(el1);
    const parentList2 = parentList(el2);

    for(let i=0; i<parentList1.length; i++){
     if(parentList2.includes(parentList1[i])){
         return parentList1[i];
     } 
    }
    return null;
}

این راه حل کار می کند ، اما به دلیل بررسی () در داخل حلقه ، پیچیدگی زمانی O (n²) دارد.

ما می توانیم این کار را با استفاده از Set برای ذخیره لیست والدین بهبود بخشیم ، تا بتوانیم از آن استفاده کنیم parentList2.has(parentList1[i])، این از O (1) پیچیدگی است ، بنابراین پیچیدگی زمان برای کد ما o (n) خواهد بود.

💡 توجه: این پست ها در درجه اول برای یادگیری و تمرین من است. منظور آنها به عنوان راهنمای رسمی نیست اما ممکن است برای کسی که برای مصاحبه آماده می شود مفید باشد.