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

# 题目

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

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

# 示例

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

# 题解

  • 前序遍历结果和中序遍历结果的长度肯定是一直的

  • 如果结果长度为0,表示树为null

  • 如果结果长度为1,那么这个肯定是树的根节点

  • 前序遍历的结果顺序是 中 -> 左 -> 右,也就是说前序遍历数组的第一项一定是一个根节点(或者子树根节点)

  • 中序遍历的结果顺序是 左 -> 中 -> 右,也就是说中序遍历结果中,根节点对应下标左侧的数据都是属于根节点的左树,右侧数据都是属于右树

  • 由此,就可以递归的去挨个构建树(子树)的根节点

# 代码实现

function buildTree (preorder, inorder) {
  if (!preorder.length || !inorder.length) {
    return null
  }
  return core(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1)
}

function core (preorder, inorder, prestart, preend, instart, inend) {
  const node = new TreeNode(preorder[prestart])
  if (prestart === preend) {
    return node
  }
  let current = instart // 根节点在中序遍历中的下标位置
  for (; current <= inend; current++) {
    if (inorder[current] === node.val) {
      break
    }
  }

  // 递归构建左右树
  const count = current - instart
  if (instart <= current - 1) {
    node.left = core(preorder, inorder, prestart + 1, prestart + count, instart, current - 1)
  }
  if (inend >= current + 1) {
    node.right = core(preorder, inorder, prestart + count + 1, preend, current + 1, inend)
  }

  return node
}

function TreeNode (val) {
  this.val = val
  this.left = this.right = null
}