hogekura avatar hogekura committed c3da757

Binary Treeの3問を追加

Comments (0)

Files changed (1)

 ;;
 
 (* Binary Trees *)
+type 'a binary_tree =
+| Empty
+| Node of 'a * 'a binary_tree * 'a binary_tree;;
+
+let rec cbal_tree n =
+  let open List.Monad_infix in
+  if n = 0 then [Empty]
+  else if n = 1 then [Node ('x', Empty, Empty)]
+  else if n mod 2 = 1 then
+    let t = cbal_tree (n / 2) in
+    t >>= fun lt ->
+    t >>= fun rt ->
+    [Node ('x', lt, rt)]
+  else
+    let t1 = cbal_tree (n / 2) in
+    let t2 = cbal_tree (n / 2 - 1) in
+    t1 >>= fun t1 ->
+    t2 >>= fun t2 ->
+    [Node ('x', t1, t2); Node ('x', t1, t2)]
+;;
+
+let rec is_mirror l r =
+  match l, r with
+  | Empty, Empty -> true
+  | Empty, Node _ | Node _, Empty -> false
+  | Node (x, ll, lr), Node (y, rl, rr) ->
+    x = y && is_mirror ll rl && is_mirror lr rr
+;;
+
+let is_symmetric = function
+  | Empty -> true
+  | Node (_, lhs, rhs) -> is_mirror lhs rhs
+;;
+
+let sym_cbal_tree n =
+  cbal_tree n |> List.filter ~f:is_symmetric ;;
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.