The following code takes input from user and output the result: For example, for the input “Haskell seems to be a very interesting language”, the output is “language interesting very a be to seems Haskell”. For example, consider the problem of reversing words in a sentence (a frequent interview question): given a string, which contains words separated by space, reverse the words. The point-free style of writing functions is particularly elegant. Haskell seems to be a very interesting language to play with. GetTree :: -> (, Tree String)īy the way, the tree is defined like this (from here):ĭata Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) the helper function to return both the tree and the rest of the string For example, given, the algorithm first creates a node with key “1” (which is the root), then it builds the left substree from, then the right substree from, which are the left substree and right substree of the root, finally it returns the root. Note that this algorithm recursively builds all the substrees and returns the root (which contains the first symbol in the list, if the list starts with a non-null symbol). Given a list of symbols, if (1) the current symbol is “#”, then remove this symbol from the list and return an empty tree (2) otherwise, create a new node with the current symbol as the key, then remove this symbol, construct the left substree from the list, then construct the right subtree from the remaining symbols in the list. The algorithm is easy to describe in an imperative fashion: to simplify things a bit, let us assume that the input is a list of strings, where each string is either “#”, which marks a null node, or a valid key, such as “123”. TreeTraverse (Node p left right) = show p ++ treeTraverse left ++ treeTraverse rightĭeserialize is the reverse of serialize: given a string (we assume that it is a valid representation of a binary tree), build a binary tree such that. TreeTraverse :: (Show a) => Tree a -> String As an example, the tree with 1 at the root, and 2 at the left substree, 3 at the right substree, is serialized as “1 2 # 3 #” (“1 (2 #) (3 #)”, which means that “2 #” is a leaf node with key 2, similarly “3 #” is a leaf node with key 3, hence “1 (2 #) (3 #)” means a node with key 1, and its left substree and right subtree are the corresponding two leaf nodes). maps a binary tree to a string: if the tree is empty, then is “#” (we use ‘#’ as a special symbol to mean “null” node) otherwise, has a non-null root, and two (possibly empty) left subtree (denoted by and right substree (denoted by, so output a string, starting with, followed by, then followed by. In fact, the problem of serialize and de-serialize binary tree in Haskell is a bit strange in the sense that by declaring the data type Tree as an instance of the Show type class, we would already have a string representation of the binary tree and using pattern matching, we also naturally have a de-serialize algorithm.)įirst let us define these two functions. (Both algorithms are essentially the same as that on leetcode. Both algorithms have a recursive flavor, as most algorithms on trees do, so I implement them with Haskell. Return sb.toString().substring(0, sb.Serialize and de-serialize a binary tree is a pair of useful little functions, especially when testing the correctness of various algorithms involving binary tree. public String serialize ( TreeNode root )
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |