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

بیان مسئله: کمترین جد مشترک یک درخت جستجوی باینری راه حل Leetcode - با توجه به درخت جستجوی دودویی (BST)، پایین ترین گره جد مشترک (LCA) را از دو گره داده شده در BST پیدا کنید. نکته: «پایین‌ترین جد مشترک بین دو گره p و q به‌عنوان پایین‌ترین گره در T که هم p و هم q را دارد تعریف می‌شود.

ادامه مطلب

دستورالعمل های گام به گام از یک گره درخت باینری به یک راه حل دیگر LeetCode

بیان مسئله: دستورالعمل های گام به گام از یک گره درخت باینری به یک راه حل LeetCode دیگر - ریشه یک درخت باینری با n گره به شما داده می شود. به هر گره مقداری از 1 تا n اختصاص داده می شود. همچنین به شما یک startValue عدد صحیح داده می شود که نشان دهنده مقدار گره شروع s است و یک عدد صحیح دیگر که نشان دهنده مقدار مقصد است…

ادامه مطلب

پیمایش ترتیب عمودی راه حل 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 می گوید که - با توجه به 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 – «جمع کردن نشانگرهای راست بعدی در هر گره» بیان می کند که با توجه به ریشه درخت دودویی کامل، باید هر اشاره گر بعدی گره را به گره سمت راست بعدی پر کنیم. اگر بعدی وجود نداشته باشد…

ادامه مطلب

Nodes را حذف کنید و راه حل Forest Leetcode را برگردانید

بیان مشکل حذف گره ها و جنگل بازگشت راه حل LeetCode – «حذف گره ها و جنگل برگرداندن» بیان می کند که با توجه به ریشه درخت دودویی که در آن هر گره دارای یک مقدار متمایز است. همچنین به ما یک آرایه به نام to_delete داده می شود که در آن باید تمام گره های دارای مقادیر موجود در …

ادامه مطلب

Translate »