Score of Parenthesis LeetCode Solution

Problem Statement The score of Parenthesis LeetCode Solution says – Given a balanced parentheses string s and return the maximum score. The score of a balanced parenthesis string is based on the following rules: “()” has score 1. AB has score A + B, where A and B are balanced parenthesis strings. (A) has score 2 * A, where A is a …

Read more

Binary Tree Inorder Traversal LeetCode Solution

Problem Statement: Binary Tree Inorder Traversal LeetCode solution Given the root of a binary tree, return the inorder traversal of its nodes’ values. Example 1: Input: root = [1,null,2,3] Output: [1,3,2] Example 2: Input: root = [] Output: [] Example 3: Input: root = [1] Output: [1] Constraints: The number of nodes in …

Read more

Decode String Leetcode Solution

Problem Statement The Decode String LeetCode Solution – “Decode String” asks you to convert the encoded string into a decoded string. The encoding rule is k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times where k is a positive integer. Example: Input: s = ”3[a]2[bc]” Output: “aaabcbc” …

Read more

Flatten Binary Tree to Linked List LeetCode Solution

Flatten Binary Tree to Linked List LeetCode Solution says that – Given the root of a binary tree, flatten the tree into a “linked list”:

  • The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
  • The “linked list” should be in the same order as a pre-order traversal of the binary tree.

 

Example 1:

Flatten Binary Tree to Linked List LeetCode SolutionInput:

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

Output:

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

Example 2:

Input:

 root = []

Output:

 []

Example 3:

Input:

 root = [0]

Output:

 [0]

 

ALGORITHM –

IDEA –

  • In order to flatten a binary tree, we will first find the rightmost element of the left subtree and after we got the rightmost element we will link the right-pointer of that node with a right subtree of a given tree.
  • In step 2 we will link the right pointer of the root node with the left-subtree and set the left-subtree as null.
  • In step 3 now our root node is a right-subtree node same process will happen with this node and the process will still continue until all the left parts become null.

Approach for Flatten Binary Tree to Linked List Leetcode Solution –

– At first, i will run a loop i.e. while(root != null) then will take two variables and store the left-subtree.

– then will check check for the rightmost node of left-subtree by using while(k.left != null) and will link that node with right subtree using (k.right = root.right).

– then link  right pointer of root node with left subtree(root.right = left) and set left pointer of root node as null(root.left=null) and will update by ( root = root.right ) so now root is right subtree node.

– this process will continue until all left-subtree parts become right subtree. Hence, the binary tree will get flattened.

 

Flatten Binary Tree to Linked List LeetCode Solution

Flatten Binary Tree to Linked List LeetCode Solution

Python Solution:

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 Solution:

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;
        }
    }
}

Time complexity: O(N)

Space Complexity: O(1)

As we have traversed only once, time complexity will be o(n).

and as we haven’t taken any extra space, space complexity will be o(1) constant extra space.

Similar Question – https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

Add Two Numbers II Leetcode Solution

Problem Statement The Add Two Numbers II LeetCode Solution – “Add Two Numbers II” states that two non-empty linked lists represent two non-negative integers where the most significant digit comes first and each node contains exactly one digit. We need to add the two numbers and return the sum as …

Read more

Daily Temperatures Leetcode Solution

Problem Statement The Daily Temperatures Leetcode Solution: states that given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead. …

Read more

Minimum Remove to Make Valid Parentheses LeetCode Solution

Problem Statement The Minimum Remove to Make Valid Parentheses LeetCode Solution – You are given a string s of ‘(‘, ‘)’ and lowercase English characters. Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is …

Read more

Trapping Rain Water Leetcode Solution

Problem Statement The Trapping Rain Water LeetCode Solution – “Trapping Rain Water” states that given an array of heights which represents an elevation map where the width of each bar is 1. We need to find the amount of water trapped after rain. Example: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: Check …

Read more

Valid Parentheses Leetcode Solution

Problem Statement The Valid Parentheses LeetCode Solution – “Valid Parentheses” states that you’re given a string containing just the characters ‘(‘, ’)’, '{‘, ’}’, '[‘ and ’]’. We need to determine whether the input string is a valid string or not. A string is said to be a valid string if open brackets must be closed …

Read more

Maximum Frequency Stack Leetcode Solution

Problem Statement The Maximum Frequency Stack LeetCode Solution – “Maximum Frequency Stack” asks you to design a frequency stack in which whenever we pop an element from the stack, it should return the most frequent element present in the stack. Implement the FreqStack class: FreqStack() constructs an empty frequency stack. void push(int val) pushes …

Read more

Translate »