LeetCode-in-Ruby.github.io

105. Construct Binary Tree from Preorder and Inorder Traversal

Medium

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1]

Output: [-1]

Constraints:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

Solution

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {Integer[]} preorder
# @param {Integer[]} inorder
# @return {TreeNode}
def build_tree(preorder, inorder)
  @j = 0
  @map = {}
  inorder.each_with_index {|val, index| @map[val] = index}
  answer(preorder, inorder, 0, preorder.length - 1)
end

private

def get(key)
  @map[key]
end

def answer(preorder, inorder, start, end_)
  return nil if start > end_ || @j > preorder.length

  value = preorder[@j]
  index = get(value)
  @j += 1
  node = TreeNode.new(value)
  node.left = answer(preorder, inorder, start, index - 1)
  node.right = answer(preorder, inorder, index + 1, end_)
  node
end

This site is open source. Improve this page.