Skip to main content

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

Date：2022-03-06 20:01:10

题目：105.从前序与中序遍历序列构造二叉树 ( 中等😕 )​

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例​

示例 1

输入: (preorder = [3, 9, 20, 15, 7]), (inorder = [9, 3, 15, 20, 7])
输出: [3, 9, 20, null, null, 15, 7]

示例 2

输入: (preorder = [-1]), (inorder = [-1])
输出: [-1]

分析​

image-20220306160049312

疑问：

  • 前序遍历的左子树右边界如何计算？

    前序遍历和中序遍历的两个左子树的长度是一致的，所以可得：

    pIndex-1 - inLeft = x - (preLeft + 1)，即：

    x = pIndex - inLeft + preLeft

  • 通过代码来看，遍历左子树时，其中序遍历左边界永远为 inLeft

    相反，遍历右子树时，其中序遍历有边界永远为 inRight，为什么？

题解​

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val
    this.left = left === undefined ? null : left
    this.right = right === undefined ? null : right
  }
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  const pLen = preorder.length
  const iLen = inorder.length
  const inorderMap = new Map<number, number>()
  for (let i = 0; i < iLen; ++i) {
    inorderMap.set(inorder[i], i)
  }

  return buildTreeRec(preorder, 0, pLen - 1, inorderMap, 0, iLen - 1)

  function buildTreeRec(
    preorder: number[],
    preLeft: number,
    preRight: number,
    inorderMap: Map<number, number>,
    inLeft: number,
    inRight: number
  ) {
    if (preLeft > preRight || inLeft > inRight) {
      return null
    }

    const val = preorder[preLeft]
    const root = new TreeNode(val)
    const pIndex = inorderMap.get(val)

    root.left = buildTreeRec(preorder, preLeft + 1, pIndex - inLeft + preLeft, inorderMap, inLeft, pIndex - 1)
    root.right = buildTreeRec(preorder, pIndex - inLeft + preLeft + 1, preRight, inorderMap, pIndex + 1, inRight)

    return root
  }
}

测试

function main() {
  const preorder = [3, 9, 20, 15, 7]
  const inorder = [9, 3, 15, 20, 7]

  console.log('[]:', buildTree(preorder, inorder))
}

main()