Count Sub Islands Solution LeetCode

بیانیه مشکل تعداد جزایر فرعی راه حل LeetCode می گوید که grid1 و grid2 فقط حاوی 0 (نماینده آب) و 1 (نماینده زمین) هستند. جزیره به معنای گروه 1 است که به صورت 4 متصل شده اند. جزیره ای در grid2 به عنوان جزیره فرعی در نظر گرفته می شود اگر جزیره ای در grid1 وجود داشته باشد که شامل تمام سلول هایی باشد که…

ادامه مطلب

پیمایش ترتیب عمودی راه حل LeetCode درخت باینری

بیان مسئله پیمایش ترتیب عمودی درخت باینری راه حل LeetCode می گوید - با توجه به ریشه یک درخت باینری، پیمایش مرتبه عمودی درخت دودویی را محاسبه کنید. برای هر گره در موقعیت (ردیف، ستون)، فرزندان چپ و راست آن به ترتیب در موقعیت‌های (ردیف + 1، col – 1) و (ردیف + 1، col + 1) قرار خواهند گرفت. …

ادامه مطلب

جمع ریشه به برگ اعداد راه حل LeetCode

بیان مسئله مجموع اعداد ریشه تا برگ LeetCode می گوید - به شما ریشه یک درخت باینری داده می شود که فقط شامل ارقام از 0 تا 9 است. هر مسیر ریشه به برگ در درخت نشان دهنده یک عدد است. به عنوان مثال، مسیر ریشه به برگ 1 -> 2 -> 3 نشان دهنده عدد 123 است. مجموع کل اعداد ریشه به برگ را برگردانید. تست …

ادامه مطلب

راه حل LeetCode پیمایش ترتیب درخت دودویی

بیان مسئله: پیمایش ترتیب درخت دودویی راه حل LeetCode با توجه به ریشه یک درخت باینری، پیمایش ترتیب مقادیر گره های آن را برگردانید. مثال 1: ورودی: ریشه = [1، تهی، 2,3،1,3,2] خروجی: [2،3،1] مثال 1: ورودی: ریشه = [] خروجی: [] مثال XNUMX: ورودی: ریشه = [XNUMX] خروجی: [XNUMX] محدودیت ها: تعداد گره ها در …

ادامه مطلب

آیا نمودار دو بخشی است؟ راه حل LeetCode

بیان مشکل نمودار LeetCode دوبخشی است راه حل - یک گراف بدون جهت با n گره وجود دارد که هر گره بین 0 و n - 1 شماره گذاری می شود. یک گراف آرایه دو بعدی به شما داده می شود، که در آن graph[u] آرایه ای از گره ها است که گره u را تشکیل می دهد. در مجاورت است. به طور رسمی تر، برای هر v در گراف[u]، یک یال بدون جهت بین گره u و گره v وجود دارد. نمودار دارای …

ادامه مطلب

طراحی افزودن و جستجوی کلمات ساختار داده راه حل LeetCode

بیان مشکل: ساختار داده کلمات را طراحی کنید و جستجو کنید راه حل LeetCode می گوید - ساختار داده ای طراحی کنید که از افزودن کلمات جدید و یافتن اینکه آیا یک رشته با رشته های قبلی اضافه شده مطابقت دارد یا خیر، طراحی کنید. پیاده سازی کلاس WordDictionary: WordDictionary() شی را مقدار دهی اولیه می کند. void addWord(word) کلمه را به ساختار داده اضافه می کند، می توان آن را بعداً مطابقت داد. جستجوی bool (کلمه) اگر وجود داشته باشد true برمی‌گرداند…

ادامه مطلب

صاف کردن درخت باینری به لیست پیوندی راه حل LeetCode

صاف کردن درخت باینری به لیست پیوندی راه حل LeetCode می گوید که - با توجه به root از یک درخت باینری، درخت را در یک "لیست پیوندی" صاف کنید:

  • «فهرست پیوندی» باید از همان استفاده کند TreeNode کلاسی که در آن right اشاره گر فرزند به گره بعدی در لیست اشاره می کند left نشانگر کودک همیشه است null.
  • "فهرست پیوندی" باید به ترتیب a باشد قبل از سفارش پیمایش از درخت دوتایی

 

به عنوان مثال 1:

صاف کردن درخت باینری به لیست پیوندی راه حل LeetCodeورودی:

 root = [1,2,5,3,4,null,6]

خروجی:

 [1,null,2,null,3,null,4,null,5,null,6]

به عنوان مثال 2:

ورودی:

 root = []

خروجی:

 []

به عنوان مثال 3:

ورودی:

 root = [0]

خروجی:

 [0]

 

الگوریتم -

اندیشه -

  • برای مسطح کردن یک درخت دودویی، ابتدا سمت راست ترین عنصر زیردرخت سمت چپ را پیدا می کنیم و پس از به دست آوردن سمت راست ترین عنصر، نشانگر سمت راست آن گره را با زیر درخت سمت راست یک درخت معین پیوند می دهیم.
  • در مرحله 2 اشاره گر سمت راست گره ریشه را با زیردرخت چپ پیوند می دهیم و زیردرخت چپ را تهی می کنیم.
  • در مرحله 3، اکنون گره ریشه ما یک گره زیردرخت راست است، همان فرآیند با این گره اتفاق می‌افتد و این روند همچنان ادامه می‌یابد تا زمانی که تمام قسمت‌های سمت چپ پوچ شوند.

رویکردی برای صاف کردن درخت باینری به لیست پیوندی راه حل Leetcode -

– در ابتدا یک حلقه اجرا می کنم یعنی while(root != null) سپس دو متغیر را می گیرد و زیر درخت سمت چپ را ذخیره می کند.

– سپس با استفاده از while(k.left != null) سمت راست ترین گره زیردرخت چپ را بررسی می کند و با استفاده از (k.right = root.right) آن گره را با زیردرخت سمت راست پیوند می دهد.

– سپس اشاره گر سمت راست گره ریشه را با زیردرخت چپ (root.right = چپ) پیوند دهید و نشانگر سمت چپ گره ریشه را به عنوان null (root.left=null) قرار دهید و با ( root = root.right ) به روز می شود، بنابراین اکنون root سمت راست است. گره زیر درخت

– این روند تا زمانی ادامه خواهد داشت که تمام قسمت های زیر درخت سمت چپ به زیردرخت سمت راست تبدیل شوند. بنابراین، درخت باینری صاف می شود.

 

صاف کردن درخت باینری به لیست پیوندی راه حل LeetCode

صاف کردن درخت باینری به لیست پیوندی راه حل LeetCode

راه حل پایتون:

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        while(root):
            
            if root.left:
                
                k = root.left
                temp = root.left
            
            
                while(k.right):
                    k = k.right
            
                k.right = root.right
            
                root.right = temp
            
                root.left = None
            
            root = root.right

راه حل جاوا:

class Solution {
    public void flatten(TreeNode root) {       
        while (root != null) {
            if (root.left != null) {
                TreeNode k = root.left;
                TreeNode temp = root.left;
                while (k.right != null) k = k.right;
                k.right = root.right;
                root.right = temp;
                root.left = null;
            }
            root = root.right;
        }
    }
}

پیچیدگی زمانی: O(N)

پیچیدگی فضا: O (1)

همانطور که فقط یک بار پیموده ایم، پیچیدگی زمانی o(n) خواهد بود.

و از آنجایی که ما هیچ فضای اضافی نگرفته ایم، پیچیدگی فضا o(1) فضای اضافی ثابت خواهد بود.

سوال مشابه - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

قطر محلول لیت کد درخت N-Ary

بیان مسئله: قطر درخت N-ARY راه حل LeetCode - با توجه به ریشه یک درخت N-ary، باید طول قطر درخت را محاسبه کنید. قطر یک درخت N-ary طول طولانی ترین مسیر بین هر دو گره در درخت است. این مسیر ممکن است یا نه…

ادامه مطلب

پایین ترین جد رایج یک راه حل لیتکد درختی باینری

بیان مشکل پایین ترین اجداد مشترک یک درخت باینری راه حل LeetCode – «پایین ترین جد مشترک درخت دودویی» بیان می کند که با توجه به ریشه درخت دودویی و دو گره درخت. ما باید کمترین جد مشترک این دو گره را پیدا کنیم. کمترین رایج…

ادامه مطلب

پر کردن اشاره گرهای راست بعدی در راه حل Leetcode هر گره

بیان مشکل پر کردن اشاره گرهای سمت راست بعدی در هر گره راه حل LeetCode – «جمع کردن نشانگرهای راست بعدی در هر گره» بیان می کند که با توجه به ریشه درخت دودویی کامل، باید هر اشاره گر بعدی گره را به گره سمت راست بعدی پر کنیم. اگر بعدی وجود نداشته باشد…

ادامه مطلب

Translate »