Here’s an approach that uses a pair of recursive functions:
defmodule TreeNode do
defstruct ~w[data left right]a
end
defmodule TreeBuild do
@nothing -1
def run([root | rest]) do
[[left, right]] = subnodes(1, rest)
%TreeNode{data: root, left: left, right: right}
end
def subnodes(0, []), do: []
def subnodes(count, input) do
{roots, rest} = Enum.split(input, 2*count)
next_count = Enum.count(roots, & &1 != @nothing)
child_nodes = subnodes(next_count, rest)
roots
|> build_nodes(child_nodes, [])
|> Enum.chunk_every(2, 2, [nil])
end
def build_nodes([], _, acc), do: Enum.reverse(acc)
def build_nodes([@nothing | roots], child_nodes, acc) do
build_nodes(roots, child_nodes, [nil | acc])
end
def build_nodes([root | roots], [], acc) do
node = %TreeNode{data: root, left: nil, right: nil}
build_nodes(roots, [], [node | acc])
end
def build_nodes([root | roots], [[left, right] | child_nodes], acc) do
node = %TreeNode{data: root, left: left, right: right}
build_nodes(roots, child_nodes, [node | acc])
end
end
TreeBuild.run([1, 2, 3, -1, -1, -1, -1])
TreeBuild.run([5,4,8,11,-1,17,4,7,-1,-1,-1,5, -1, -1, -1, -1])
Some notes on the implementation:
- the sample input has one fewer -1 on the end than I expected at first; this version of
build_nodesis tolerant of any number of trailing -1s. chunk_everyis used to tidily handle cases wherebuild_nodesreturns an odd number of nodes by providing anilforleftovers
@Eiji I believe the error in your diagram is the two -1s under the -1 that’s a right-child of 4. -1s on a given level shouldn’t consume any input values in the next level.
