Serialize and Deserialize Binary Tree - Python Leetcode

 Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

 

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

class Codec:
    '''       O(n) time and O(n) space, BFS traversal
    e.g., 1
         / \
        2   5
       / \
      3   4  , level order traversal, serialize will be '1,2,5,3,4,None,None,None,None,None,None,'; deserialize 
      with queue as well, convert back. Time and Space O(n).
    '''
    def serialize(self, root):
        if not root:
            return ''
        queue = collections.deque()
        queue.append(root)
        res = ''
        while queue:
            node = queue.popleft()
            if not node:
                res += 'None,'
                continue
            res += str(node.val) + ','
            queue.append(node.left)
            queue.append(node.right)
        return res
            
    def deserialize(self, data):
        if not data:
            return None
        ls = data.split(',')
        root = TreeNode(int(ls[0]))
        queue = collections.deque()
        queue.append(root)
        i = 1
        while queue and i < len(ls):
            node = queue.popleft()
            if ls[i] != 'None':
                left = TreeNode(int(ls[i]))
                node.left = left
                queue.append(left)
            i += 1
            if ls[i] != 'None':
                right = TreeNode(int(ls[i]))
                node.right = right
                queue.append(right)
            i += 1
        return root

        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

Find Duplicate Subtrees - Python Leetcode

  Find Duplicate Subtrees

Given the root of a binary tree, return all duplicate subtrees.

For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with the same node values.

 

Example 1:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

Example 2:

Input: root = [2,1,1]
Output: [[1]]

Example 3:

Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        count = collections.Counter()
        trees = collections.defaultdict()
        trees.default_factory = trees.__len__
        ans = []
        def lookup(root):
            if root:
                uid = trees[root.val,lookup(root.left),lookup(root.right)]
                count[uid]+=1
                if count[uid] == 2:
                    ans.append(root)
                return uid
        
        lookup(root)
        return ans
        

TC: O(n) SC: O(n)

Next Closest Time

 Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, "01:34", "12:09" are all valid. "1:34", "12:9" are all invalid.

Example 1:

Input: "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.  It is not 19:33, because this occurs 23 hours and 59 minutes later.

Example 2:

Input: "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.

class Solution(object):
    def nextClosestTime(self, time):
        cur = 60 * int(time[:2]) + int(time[3:])
        allowed = {int(x) for x in time if x != ':'}
        while True:
            cur = (cur + 1) % (24 * 60)
            if all(digit in allowed
                    for block in divmod(cur, 60)
                    for digit in divmod(block, 10)):
                return "{:02d}:{:02d}".format(*divmod(cur, 60))

TC : O(1) max 24*60 iterations

SC : O(1) 

Top Interview Questions for Software Engineer (Google , Microsoft , Amazon , Uber , Airbnb)

 Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            if target-nums[i] in hashmap:
                return [i,hashmap[target-nums[i]]]
            else:
                hashmap[nums[i]] = i
        return []
            

TC : O(n) // Iterating over each element . SC: O(n) Extra space for Hashmap.

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
            tailA = l1
            tailB = l2
            carry = 0
            dummyHead = ListNode(-1)
            resNode = dummyHead
            while tailA or tailB:
                x = tailA.val if tailA else 0
                y = tailB.val if tailB else 0
                val = x + y + carry
                resNode.next = ListNode(val % 10)
                carry = val // 10
                if tailA: tailA = tailA.next 
                if tailB: tailB = tailB.next
                resNode = resNode.next
                
            if carry == 1:
                resNode.next = ListNode(carry)
                resNode = resNode.next
     
            return dummyHead.next

TC : O(max(m,n)) SC: O(max(m,n)+1)

Strobogrammatic Number - Python Leetcode

 A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

 

Example 1:

Input: num = "69"
Output: true

Example 2:

Input: num = "88"
Output: true

Example 3:

Input: num = "962"
Output: false

Example 4:

Input: num = "1"
Output: true

TC: O(N) SC:O(1)

Solution 1:

class Solution:
    def isStrobogrammatic(self, num: str) -> bool:
        if not num:
            return True
        map = {'0':'0','1':'1','6':'9','8':'8','9':'6','2':'','3':'','4':'','5':'','7':''}
        i = 0
        j = len(num)-1
        while i<=j:
            if num[i] != map[num[j]]:
                return False
            i+=1
            j-=1
        return True

Solution 2:

class Solution:
    def isStrobogrammatic(self, num: str) -> bool:
        if not num:
            return True
        map = {'0':'0','1':'1','6':'9','8':'8','9':'6'}
        i = 0
        j = len(num)-1
        while i<=j:
            if num[j] not in map or num[i] != map[num[j]]:
                return False
            i+=1
            j-=1
        return True
    

Isomorphic Strings - Python Leetcode Solution

 Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        if s==t or (s is None and t is None):
            return True
        if len(s) != len(t):
            return False
        map = {}
        for i in range(len(s)):
            if s[i] not in map and t[i] not in map.values(): 
                map[s[i]] = t[i] 
            if s[i] not in map or map[s[i]] != t[i]:  
                return False
            
        return True
 

Invert Binary Tree - Leetcode Python Solution

 Invert a binary tree.

Example:

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Iterative approcah . 

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, val=0, left=None, right=None):

#         self.val = val

#         self.left = left

#         self.right = right

class Solution:

    def invertTree(self, root: TreeNode) -> TreeNode:

        if not root:

            return None

        q = []

        q.append(root)

        while q:

            curr = q.pop()

            curr.left , curr.right = curr.right,curr.left

            if curr.left:

                q.append(curr.left)

            if curr.right:

                q.append(curr.right)

        return root

            

        TC: O(n)

        SC: O(n) in worst case where queue is completely occupied. 

Recursive approch:

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, val=0, left=None, right=None):

#         self.val = val

#         self.left = left

#         self.right = right

class Solution:

    def invertTree(self, root: TreeNode) -> TreeNode:

        if not root:

            return None

        curr = root

        if curr.left:

            self.invertTree(curr.left)

        if curr.right:

            self.invertTree(curr.right)

        curr.left,curr.right = curr.right,curr.left

        return root

            

    Recursive approach:

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, val=0, left=None, right=None):

#         self.val = val

#         self.left = left

#         self.right = right

class Solution:

    def invertTree(self, root: TreeNode) -> TreeNode:

        if not root:

            return None

        curr = root

        curr.left,curr.right = curr.right,curr.left

        if curr.left:

            self.invertTree(curr.left)

        if curr.right:

            self.invertTree(curr.right)

        return root

            

       TC: O(n)

       SC: O(n)