889. Construct Binary Tree from Preorder and Postorder Traversal [JavaScript]

一、題目

  Return any binary tree that matches the given preorder and postorder traversals.

  Values in the traversals pre and post are distinct positive integers.

二、題目大意

  根據二叉樹的前序和後序序列建構二叉樹。(并且序列中無重複的元素，這一點很重要。)

三、解題思路

  首先需要了解前序周遊和後序周遊：

前序周遊 root(left)(right)

  後序周遊 (left)(right)root
           

  對于根節點很容易可以拿到，關鍵就是找到左子樹和右子樹的分割點，進而遞歸建構左右子樹。

四、代碼實作

const constructFromPrePost = (pre, post) => {

  if (pre.length === 0) {
    return null
  }
  // 拿出根節點
  const x = pre.shift()
  post.pop()

  const root = new TreeNode(x)

  if (pre.length > 0) {
    // 找到左右子樹的分割點，這也是為什麼不能存在重複元素的原因。
    const l = pre[0]
    const lIndex = post.indexOf(l)

    root.left = constructFromPrePost(pre.slice(0, lIndex + 1), post.slice(0, lIndex + 1))
    root.right = constructFromPrePost(pre.slice(lIndex + 1), post.slice(lIndex + 1))
  }
  return root
}
           

  如果本文對您有幫助，歡迎關注微信公衆号，為您推送更多大前端相關的内容， 歡迎留言讨論，ε=ε=ε=┏(゜ロ゜;)┛。

  您還可以在這些地方找到我：

• 一個前端開發者的LeetCode刷題之旅
• 掘金