ലിങ്ക്ഡ് ലിസ്റ്റ് LeetCode സൊല്യൂഷനിലേക്ക് ബൈനറി ട്രീ പരത്തുക എന്ന് പറയുന്നു - നൽകിയിരിക്കുന്നത് root ഒരു ബൈനറി ട്രീയുടെ, വൃക്ഷത്തെ ഒരു "ലിങ്ക്ഡ് ലിസ്റ്റ്" ആയി പരത്തുക:

• "ലിങ്ക് ചെയ്ത ലിസ്റ്റ്" അത് തന്നെ ഉപയോഗിക്കണം TreeNode ക്ലാസ് എവിടെ right ചൈൽഡ് പോയിന്റർ ലിസ്റ്റിലെ അടുത്ത നോഡിലേക്കും ദി left കുട്ടി സൂചിക എപ്പോഴും null.
• "ലിങ്ക് ചെയ്‌ത പട്ടിക" a-യുടെ അതേ ക്രമത്തിലായിരിക്കണം പ്രി ഓർഡർ ട്രാവെർസൽ ബൈനറി ട്രീയുടെ.

 

ഉദാഹരണം 1:

ഇൻപുട്ട്:

 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(റൂട്ട് != null) തുടർന്ന് രണ്ട് വേരിയബിളുകൾ എടുത്ത് ഇടത്-സബ്‌ട്രീ സംഭരിക്കും.

– തുടർന്ന് while(k.left != null) ഉപയോഗിച്ച് ഇടത്-സബ്‌ട്രീയുടെ വലത്തേയറ്റത്തെ നോഡ് പരിശോധിക്കുകയും ആ നോഡിനെ വലത് സബ്‌ട്രീയുമായി ലിങ്ക് ചെയ്യുകയും ചെയ്യും (k.right = root.right).

– തുടർന്ന് റൂട്ട് നോഡിന്റെ വലത് പോയിന്റർ ഇടത് സബ്ട്രീ (root.right = ഇടത്) ഉപയോഗിച്ച് ലിങ്ക് ചെയ്യുകയും റൂട്ട് നോഡിന്റെ ഇടത് പോയിന്റർ null (root.left=null) ആയി സജ്ജമാക്കുകയും (root.left=null) ആയി അപ്‌ഡേറ്റ് ചെയ്യുകയും ചെയ്യും, അതിനാൽ ഇപ്പോൾ റൂട്ട് ശരിയാണ് സബ്ട്രീ നോഡ്.

- എല്ലാ ഇടത്-സബ്ട്രീ ഭാഗങ്ങളും വലത് സബ്ട്രീ ആകുന്നത് വരെ ഈ പ്രക്രിയ തുടരും. അതിനാൽ, ബൈനറി മരം പരന്നുപോകും.

 

പൈത്തൺ പരിഹാരം:

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