Skip to main content

Leetcode 449. Serialize and Deserialize BST. Python (DFS)

449Serialize and Deserialize BST




Serialization is 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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

 

Example 1:

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

Example 2:

Input: root = []
Output: []

 

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • 0 <= Node.val <= 104
  • The input tree is guaranteed to be a binary search tree.


Solution :

class Codec:

    def serialize(self, root: Optional[TreeNode]) -> str:
        self.ans = []
        
        def dfs(node):
            if not node: return
            self.ans.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        
        dfs(root)
        return ",".join(self.ans)
        

    def deserialize(self, data: str) -> Optional[TreeNode]:
        if not data: return None
        ans = [int(d) for d in data.split(",")]
        
        
        def dfs(ans, l, u):
            if not ans: return None
            if not l <= ans[0] <= u : return None
            
            node = ans.pop(0) #O(n)
            root = TreeNode(node)
            
            root.left = dfs(ans, l, root.val)
            root.right = dfs(ans, root.val, u)
            
            return root
        return dfs(ans, -float('inf'), float('inf'))



 Explaination :



Comments

Popular posts from this blog

Leetcode 371. Sum of Two Integers. C++ / Java

371 .  Sum of Two Integers   Given two integers  a  and  b , return  the sum of the two integers without using the operators   +   and   - .   Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5   Constraints: -1000 <= a, b <= 1000 Solution :  C++ : class Solution { public: int getSum(int a, int b) { if (b==0) return a; int sum = a ^ b; int cr = (unsigned int) (a & b) << 1; return getSum(sum, cr); } }; Java :  class Solution { public int getSum(int a, int b) { while(b != 0){ int tmp = (a & b) << 1; a = a ^ b; b = tmp; } return a; } } Explaination :

Leetcode 217. Contains Duplicate. Python (Easiest Approach ✅)

217 .  Contains Duplicate   Given an integer array  nums , return  true  if any value appears  at least twice  in the array, and return  false  if every element is distinct.   Example 1: Input: nums = [1,2,3,1] Output: true Example 2: Input: nums = [1,2,3,4] Output: false Example 3: Input: nums = [1,1,1,3,3,4,3,2,4,2] Output: true   Constraints: 1 <= nums.length <= 10 5 -10 9  <= nums[i] <= 10 9 class Solution: def containsDuplicate(self, nums: List[int]) -> bool: hs = set() for n in nums: if n in hs: return True hs.add(n) return False Explaination :

Number of Connected Components in an Undirected Graph (Python)

66.  Number of Connected Components in an Undirected Graph Question Link :  check here Givennnodes labeled from0ton - 1and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph. Example 1:      0          3      |          |      1 --- 2    4 Givenn = 5andedges = [[0, 1], [1, 2], [3, 4]], return2. Example 2:      0           4      |           |      1 --- 2 --- 3 Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [3, 4]], return1. Note: You can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges. Solution : class Solution: def counComponents(self, n: int, edges : List[List[int]]) -> i...