LeetCode Q105 https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

q105.livemd

Solution to LeetCode Q 105. Construct Binary Tree from Preorder and Inorder Traversal

Section

Solution to 105. Construct Binary Tree from Preorder and Inorder Traversal problem on LeetCode.

Code

# Setup given implicitly by exercise.
defmodule TreeNode do
  @type t :: %__MODULE__{
          val: integer,
          left: TreeNode.t() | nil,
          right: TreeNode.t() | nil
        }
  defstruct val: 0, left: nil, right: nil
end

{:module, TreeNode, <<70, 79, 82, 49, 0, 0, 7, ...>>, %TreeNode{left: nil, right: nil, val: 0}}

# Solution
defmodule Solution do
  @spec build_tree(preorder :: [integer], inorder :: [integer]) :: TreeNode.t() | nil
  def build_tree([p | ps], inorder) do
    {left_is, right_is} = Enum.split_while(inorder, &(&1 != p))
    # get rid of the split, which is the root
    right_is = Enum.drop(right_is, 1)
    {left_ps, right_ps} = Enum.split(ps, length(left_is))
    %TreeNode{val: p, left: build_tree(left_ps, left_is), right: build_tree(right_ps, right_is)}
  end

  def build_tree([], []), do: nil
end

{:module, Solution, <<70, 79, 82, 49, 0, 0, 8, ...>>, {:build_tree, 2}}

# test with given example
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
Solution.build_tree(preorder, inorder)

%TreeNode{
  left: %TreeNode{left: nil, right: nil, val: 9},
  right: %TreeNode{
    left: %TreeNode{left: nil, right: nil, val: 15},
    right: %TreeNode{left: nil, right: nil, val: 7},
    val: 20
  },
  val: 3
}