Lstmxx的空间

105. 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

链接

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  return build(
    preorder, 0, preorder.length - 1,
    inorder, 0, inorder.length - 1
  )
}

function build(
  preorder: number[], preStart: number, preEnd: number,
  inorder: number[], inStart: number, inEnd: number
): TreeNode | null {
  if (preStart > preEnd) return null
  const rootVal = preorder[preStart]
  let index = 0
  for(let i = inStart;i <= inEnd;i++) {
    if (inorder[i] === rootVal) {
      index = i
      break
    }
  }
  const leftSize = index - inStart
  const root = new TreeNode(rootVal)
  root.left = build(
    preorder, preStart + 1, preStart + leftSize,
    inorder, inStart, index - 1
  )
  root.right = build(
    preorder, preStart + leftSize + 1, preEnd,
    inorder, index + 1, inEnd
  )
  return root
}