-
Notifications
You must be signed in to change notification settings - Fork 1
/
ListToTree.hs
141 lines (112 loc) · 2.54 KB
/
ListToTree.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
module Main where
import BinaryTree (BinaryTree (..), valuesPreOrder)
import Control.Monad (guard)
import Data.Maybe (fromJust, isJust)
{-
@onelharrison - [Twitter | Medium]
data BinaryTree a = Empty
| Leaf a
| Node (BinaryTree a) a (BinaryTree a)
deriving (Show, Eq)
Description
-----------
Write a function that deserializes a preorder string-encoded binary tree.
(String -> BinaryTree Char) . (BinaryTree Char -> String) = BinaryTree Char -> BinaryTree Char
?? . valuesPreOrder
The following defines the set of valid values in the encoded tree.
p node
- parent node
- internal node
- root node if root node has at least 1 child node
w node
- leaf node
- left child of a p-node
b node
- leaf node
- right child of a p-node
Examples
--------
Input: ""
Output: Empty
Input: "w"
Output: Leaf 'w'
Explanation
w
Input: "b"
Output: Leaf 'b'
Explanation:
b
Input: "p"
Output: Invalid input
Explanation: root node without any children cannot be a p-node
Input: "pw"
Output: Node (Leaf 'w') 'p' Empty
Explanation:
p
/
w
Input: "pb"
Output: Node Empty 'p' (Leaf 'b')
Explanation:
p
\
b
Input: "pp"
Output: Invalid input
Explanation: p-node cannot be leaf node
Input: "pwpwb"
Output: Node (Leaf 'w') 'p' (Node (Leaf 'w') 'p' (Leaf 'b'))
Explanation:
p
/ \
w p
/ \
w b
Input: "ppwb"
Output: Node (Node (Leaf 'w') 'p' (Leaf 'b')) 'p' Empty
Explanation:
p
/
p
/ \
w b
Input: "pwppwb"
Output: Node (Leaf 'w') 'p' (Node (Node (Leaf 'w') 'p' (Leaf 'b)) 'p' Empty)
Explanation:
p
/ \
w p
/
p
/ \
w b
data BinaryTree a = Empty
| Leaf a
| Node (BinaryTree a) a (BinaryTree a)
deriving (Show, Eq)
-}
preOrderToTree :: String -> Maybe (BinaryTree Char)
preOrderToTree "" = Just Empty
preOrderToTree "w" = Just (Leaf 'w')
preOrderToTree "b" = Just (Leaf 'b')
preOrderToTree ('p':'w':xs) = do
lst <- preOrderToTree "w"
rst <- preOrderToTree xs
return (Node lst 'p' rst)
preOrderToTree ('p':'b':xs) =
if null xs
then do
rst <- preOrderToTree "b"
return (Node Empty 'p' rst)
else Nothing
preOrderToTree ('p':'p':xs) = do
lst <- preOrderToTree ('p' : xs)
return (Node lst 'p' Empty)
preOrderToTree _ = Nothing
main :: IO ()
main = do
str <- getLine
let tree = preOrderToTree . head . lines $ str
print tree
guard (isJust tree)
print . valuesPreOrder $ fromJust tree