Lstmxx的空间

106. 从中序与后序遍历序列构造二叉树

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

注意:
你可以假设树中没有重复的元素。

链接

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

function build(
  inorder: number[], inStart: number, inEnd: number,
  postorder: number[], postStart: number, postEnd: number
): TreeNode | null {
  if (inStart > inEnd) return null
  const rootVal = postorder[postEnd]
  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(
    inorder, inStart, index - 1,
    postorder, postStart, postStart + leftSize - 1
  )
  root.right = build(
    inorder, index + 1, inEnd,
    postorder, postStart + leftSize, postEnd - 1
  )
  return root
}