My Muri Life

切换主题

本页目录

二叉树的还原 ​

前序与中序 ​

从前序遍历序列与中序遍历序列还原二叉树！

还原过程描述:

  1. 在前序序列preorder中找到根节点值rootVal；
  2. 根据rootVal在中序序列inorder中找到其对应的下标rootIdx，即根节点的左右子树的分界点；
  3. 创建根节点root后，递归地生成左子树root.left、右子树root.right；
  4. 最后返回root。
JavaScript
const buildTree = (preorder, inorder) => {
  if (!preorder.length || !inorder.length) return null
  const rootVal = preorder.shift()  // 这里改变了preorder
  const rootIdx = inorder.indexOf(rootVal)
  const root = new TreeNode(rootVal)
  root.left = buildTree(preorder.slice(0, rootIdx), inorder.slice(0, rootIdx))
  root.right = buildTree(preorder.slice(rootIdx), inorder.slice(rootIdx + 1))
  return root
}

时间复杂度：O(n^2)；空间复杂度：O(n)。

优化 ​

  1. 使用hashMap优化Array#indexOf函数在中序序列中的查找;
  2. 使用指针 优化Array#slice函数对左右子树的截取。
JavaScript
const buildTree = (preorder, inorder) => {
  if (!preorder.length || !inorder.length) return null
  const map = new Map()
  for (let i = 0; i < inorder.length; i++) {
    map.set(inorder[i], i)
  }
  const build = (preStart, preEnd, inStart, inEnd) => {
    if (preStart > preEnd) return null
    const rootVal = preorder[preStart]
    const rootIdx = map.get(rootVal)
    const root = new TreeNode(rootVal)
    const leftNodes = rootIdx - inStart  // 左子树节点数
    root.left = build(preStart + 1, preStart + leftNodes, inStart, rootIdx - 1)
    root.right = build(preStart + leftNodes + 1, preEnd, rootIdx + 1, inEnd)
    return root
  }
  return build(0, preorder.length - 1, 0, inorder.length - 1)
}

时间复杂度：O(n)；空间复杂度：O(n)。

再次优化 ​

不使用额外的map空间，在剩余的完整的中序序列inorder上递归，当在inorder遇到stop时（即根节点root）就停止。

JavaScript
const buildTree = (preorder, inorder) => {
  let [i, j] = [0, 0]
  const build = stop => {
    if (inorder[i] != stop) {
      const root = new TreeNode(preorder[j++])
      root.left = build(root.val)  // 左子调用提供 自己的根值 作为stop
      i++
      root.right = build(stop) // 右子调用提供 其父级的stop 作为stop
      return root
    }
    return null
  }
  return build()
}

时间复杂度：O(n)；空间复杂度：O(n)。

中序与后序 ​

从中序遍历序列与后序遍历序列还原二叉树！

还原过程描述:

  1. 在后序序列postorder中找到根节点值rootVal；
  2. 根据rootVal在中序序列inorder中找到其对应的下标rootIdx，即根节点的左右子树的分界点；
  3. 创建根节点root后，递归地生成左子树root.left、右子树root.right；
  4. 最后返回root。
JavaScript
const buildTree = (inorder, postorder) => {
  if (!inorder.length || !postorder) return null
  const rootVal = postorder.pop()  // 这里改变了postorder
  const rootIdx = inorder.indexOf(rootVal)
  const root = new TreeNode(rootVal)
  root.left = buildTree(inorder.slice(0, rootIdx), postorder.slice(0, rootIdx))
  root.right = buildTree(inorder.slice(rootIdx + 1), postorder.slice(rootIdx))
  return root
}

时间复杂度：O(n^2)；空间复杂度：O(n)。

优化 ​

  1. 使用hashMap优化Array#indexOf函数在中序序列中的查找;
  2. 使用指针 优化Array#slice函数对左右子树的截取。
JavaScript
const buildTree = (inorder, postorder) => {
  if (!inorder.length || !postorder) return null
  const map = new Map()
  for (let i = 0; i < inorder.length; i++) {
    map.set(inorder[i], i)
  }
  const build = (inStart, inEnd, postStart, postEnd) => {
    if (postStart > postEnd) return null
    const rootVal = postorder[postEnd]
    const rootIdx = map.get(rootVal)
    const root = new TreeNode(rootVal)
    const leftNodes = rootIdx - inStart
    root.left = build(inStart, rootIdx - 1, postStart, postStart + leftNodes - 1)
    root.right = build(rootIdx + 1, inEnd, postStart + leftNodes, postEnd - 1)
    return root
  }
  return build(0, inorder.length - 1, 0, postorder.length - 1)
}

时间复杂度：O(n)；空间复杂度：O(n)。

再次优化 ​

不使用额外的map空间，在剩余的完整的中序序列inorder上递归，当在inorder遇到stop时（即根节点root）就停止。

JavaScript
const buildTree = (inorder, postorder) => {
  let [i, j] = [inorder.length - 1, postorder.length - 1]
  const build = stop => {
    if (inorder[i] != stop) {
      const root = new TreeNode(postorder[j--])
      root.right = build(root.val)  // 右子调用提供 自己的根值 作为stop
      i--
      root.left = build(stop) // 左子调用提供 其父级的stop 作为stop
      return root
    }
    return null
  }
  return build()
}

时间复杂度：O(n)；空间复杂度：O(n)。

前序与后序 ​

从前序遍历序列与后序遍历序列还原二叉树！

还原过程描述:

  1. 前序序列的第一个元素是根节点，我们使用数组的Array#shift方法，来维持子序列的这一特性；
  2. 后序序列的最后一个元素是根节点，我们使用数组的Array#pop方法，来维持子序列的这一特性；
  3. 接下来根据前序序列的左子树前序序列 -> 右子树前序序列和后序序列的左子树后序序列 -> 右子树后序序列找左右子树的分界点，此时有两种方法：
    1. 拿左子树的前序序列的第一个元素在后序序列中找左子树后序序列和右子树后序序列的分界点idx；
    2. 拿右子树的后序序列的最后一个元素在先序序列中找左子树先序序列和右子树先序序列的分界点idx。
  4. 因为.shift(0, idx)方法在拷贝数组时，拷贝区间是[0, idx)，而此时：
    1. 情况3.1中的idx是左子树后序序列上的最后一个节点，必须拷贝的，所以有了idx+1；
    2. 情况3.2中的idx是右子树先序序列的起始节点位置，直接取idx。
  5. 然后递归生成左子树、右子树；
  6. 最后返回root。
JavaScript
const buildTree = (preorder, postorder) => {
  if (!preorder.length || !postorder.length) return null
  const root = new TreeNode(preorder.shift())
  postorder.pop()
  if (preorder.length) {
    const idx = postorder.indexOf(preorder[0]) + 1  // 3.1
    // const idx = preorder.indexOf(postorder[postorder.length-1])  // 3.2
    root.left = buildTree(preorder.slice(0, idx), postorder.slice(0, idx))
    root.right = buildTree(preorder.slice(idx), postorder.slice(idx))
  }
  return root
}

时间复杂度：O(n^2)；空间复杂度：O(n^2)。

数据结构应用 ​

leetcode
  1. 105. 从前序与中序遍历序列构造二叉树
  2. 106. 从中序与后序遍历序列构造二叉树
  3. 889. 从前序和后序遍历序列构造二叉树