Added PreOrder Approach

PriyankaKhire · PriyankaKhire · commit e108b8d81b11 · 2021-08-21T21:40:14.000-07:00
Leetcode Accepted
diff --git a/Blind 75/Programs/Serialize and Deserialize Binary Tree - PreOrder.py b/Blind 75/Programs/Serialize and Deserialize Binary Tree - PreOrder.py
@@ -0,0 +1,66 @@
+# Serialize and Deserialize Binary Tree
+# https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
+
+# Definition for a binary tree node.
+# class TreeNode(object):
+#     def __init__(self, x):
+#         self.val = x
+#         self.left = None
+#         self.right = None
+
+class Codec:
+    
+    def preOrder(self, node, array):
+        if not node:
+            array.append("null")
+            return
+        array.append(str(node.val))
+        self.preOrder(node.left, array)
+        self.preOrder(node.right, array)
+        
+    def serialize(self, root):
+        array = []
+        self.preOrder(root, array)
+        # Join the result using comma as delimiter.
+        return ",".join(array)
+        """Encodes a tree to a single string.
+        :type root: TreeNode
+        :rtype: str
+        """
+    def createNode(self, val):
+        return TreeNode(int(val))
+    
+    def preOrderCreateTree(self, array, index):
+        # The reason why we use index as list and not a single number is because a single number gets modified within recurssive calls but a list does not.
+        if (index[0] > len(array) or array[index[0]] == 'null'):
+            return
+        # Create the node with the value.
+        node = self.createNode(array[index[0]])
+        # Increment the index and get the left side of the node.
+        index[0] = index[0] + 1
+        node.left = self.preOrderCreateTree(array, index)
+        # Increment the index and get the right side of the node.
+        index[0] = index[0] + 1
+        node.right = self.preOrderCreateTree(array, index)
+        # Return this node, so it can be added to left or right of the calling parent.
+        return node
+
+    def deserialize(self, data):
+        if not data:
+            return []
+        # Split the data into a list, using comma as delimiter.
+        nodeList = data.split(",")
+        # Create the tree.
+        node = self.preOrderCreateTree(nodeList, [0])
+        # Return the root of the tree.
+        return node
+        """Decodes your encoded data to tree.
+        :type data: str
+        :rtype: TreeNode
+        """
+        
+
+# Your Codec object will be instantiated and called as such:
+# ser = Codec()
+# deser = Codec()
+# ans = deser.deserialize(ser.serialize(root))
diff --git a/Blind 75/README.md b/Blind 75/README.md
@@ -222,13 +222,16 @@
       <li><a href="Programs/Binary Tree Level Order Traversal.py">Binary Tree Level Order Traversal</a>
         <p><b>Approach</b>: Used a modified iterative BFS</p>
       </li>
-      <li>Serialize and Deserialize Binary Tree
+      <li><a href="Programs/Serialize and Deserialize Binary Tree - PreOrder.py">Serialize and Deserialize Binary Tree</a> 
+        <p><b>Approach</b>: Use preorder to serialize it using comma as delimiter. <br/>
+          Then use similar method we use to find height of tree to first add left child of sub tree and then add right child of sub tree, all while traversing the array.
+        </p>
         <p><b>Thoughts</b>: Initially I thought of using tries to do this, but it can create problems if all nodes of the tree have same value. <br/>
           My next thought was to do inOrder and preOrder traversal and then build the tree, but I was plagued by the same above problem, what if all tree nodes have same value. <br/>
           Then I thought about level order traversal but use delimiter for null nodes, this will waste a LOT of space (what if the tree is skewed), but I will end up with correct answer. <br/>
         </p>
         <ul>
-          <li><a href="Programs/Serialize and Deserialize Binary Tree - LevelOrder Toomuch Space.py">Too much space with level order</a> </li>
+          <li><a href="Programs/Serialize and Deserialize Binary Tree - LevelOrder Toomuch Space.py">Too much space with level order</a>: This exceeded leetcode space limit. </li>
         </ul>
       </li>
       <li>Subtree of Another Tree</li>
