ချိတ်ဆက်ထားသောစာရင်း LeetCode ဖြေရှင်းချက်သို့ Flatten Binary Tree ပေးသည် ဟုဆိုသည်။ root ဒွိစုံသစ်ပင်၏ “ချိတ်ဆက်ထားသောစာရင်း” အဖြစ် သစ်ပင်ကို ပြားချပ်စေသည်-

• "လင့်ခ်ချိတ်ထားသောစာရင်း" သည် အလားတူအသုံးပြုသင့်သည်။ TreeNode အတန်းဘယ်မှာလဲ။ right ကလေးညွှန်ပြချက်သည် စာရင်းရှိ နောက် node ကို ညွှန်ပြသည်။ left ကလေးညွှန်းကိန်းသည် အမြဲတမ်းဖြစ်သည်။ null.
• "လင့်ခ်ချိတ်ထားသောစာရင်း" သည် a ကဲ့သို့ အစဉ်လိုက်ရှိသင့်သည်။ ကြိုတင်မှာယူမှု ဖြတ်သန်း ဒွိသစ်ပင်၏။

 

ဥပမာအား 1:

input:

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

output:

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

ဥပမာအား 2:

input:

 root = []

output:

 []

ဥပမာအား 3:

input:

 root = [0]

output:

 [0]

 

အယ်လ်ဂိုရစ်သမ် –

IDEA –

• ဒွိသစ်ပင်တစ်ပင်ကို ပြားချပ်စေရန်အတွက်၊ ဘယ်ဘက်သစ်ပင်၏ ညာဘက်ဆုံးဒြပ်စင်ကို ဦးစွာရှာတွေ့မည်ဖြစ်ပြီး ညာဘက်ဆုံးဒြပ်စင်ကိုရပြီးနောက် ပေးထားသောသစ်ပင်၏ ညာဘက်အခွဲနှင့် ထိုနိတ်၏ညာဘက်ညွှန်သူကို ချိတ်ဆက်မည်ဖြစ်သည်။
• အဆင့် 2 တွင်ကျွန်ုပ်တို့သည် root node ၏ညာဘက်ညွှန်ပြချက်ကိုဘယ်-subtree နှင့်ချိတ်ဆက်ပြီး left-subtree ကို null အဖြစ်သတ်မှတ်မည်ဖြစ်သည်။
• ယခု အဆင့် 3 တွင် ကျွန်ုပ်တို့၏ root node သည် right-subtree node တစ်ခုဖြစ်ပြီး တူညီသောလုပ်ငန်းစဉ်သည် ဤ node နှင့်ဖြစ်သွားမည်ဖြစ်ပြီး၊ ဘယ်ဘက်အပိုင်းများအားလုံး null ဖြစ်သွားသည်အထိ လုပ်ငန်းစဉ်သည် ဆက်လက်ရှိနေမည်ဖြစ်သည်။

ချိတ်ဆက်ထားသောစာရင်း Leetcode ဖြေရှင်းချက်သို့ Flatten Binary Tree အတွက်ချဉ်းကပ်နည်း

– ပထမတော့၊ ငါ while(root != null) ဖြစ်တဲ့ loop တစ်ခုကို run မယ် ပြီးရင် variable နှစ်ခုကိုယူပြီး ဘယ်ဘက် subtree ကို သိမ်းမယ်။

- ထို့နောက် while(k.left != null) ကို အသုံးပြု၍ ဘယ်ဘက်အခွဲ၏ ညာဖက်အစွန်းကို စစ်ဆေးမည်ဖြစ်ပြီး (k.right = root.right) ကို အသုံးပြု၍ အဆိုပါ node နှင့် ညာဖက်အခွဲနှင့် ချိတ်ဆက်ပေးမည်ဖြစ်သည်။

- ထို့နောက် root node ၏ ညာဘက်ညွှန်ပြချက်ကို ဘယ်ဘက်အခွဲ(root.right=left) ဖြင့် လင့်ခ်ချိတ်ပြီး root node ၏ ဘယ်ဘက်ညွှန်ပြချက်ကို null(root.left=null) အဖြစ် သတ်မှတ်ပြီး ( root = root.right ) ဖြင့် အပ်ဒိတ်လုပ်မည်ဖြစ်သောကြောင့် ယခု root သည် မှန်ကန်ပါသည်။ subtree node များ။

- ဘယ်ဘက်-သစ်ပင် အစိတ်အပိုင်းများအားလုံး ညာဘက်သစ်ပင်ဖြစ်လာသည်အထိ ဤလုပ်ငန်းစဉ်ကို ဆက်လက်လုပ်ဆောင်ပါမည်။ ထို့ကြောင့် ဒွိစုံပင်သည် ပြားသွားလိမ့်မည်။

 

Python ဖြေရှင်းချက်-

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

Java ဖြေရှင်းချက်-

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)

အာကာသရှုပ်ထွေး: အို (1)

တစ်ကြိမ်သာ ဖြတ်ကျော်ပြီးသည်နှင့်အမျှ အချိန်၏ရှုပ်ထွေးမှုသည် o(n) ဖြစ်လိမ့်မည်။

အပိုနေရာမယူထားသောကြောင့်၊ space complexity သည် o(1) constant extra space ဖြစ်လိမ့်မည်။

အလားတူမေးခွန်း- https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm