105. Construct Binary Tree from Preorder and Inorder Traversal [JavaScript]

一、題目

  Given preorder and inorder traversal of a tree, construct the binary tree.

  You may assume that duplicates do not exist in the tree.

二、題目大意

  根據前序周遊序列和中序周遊序列建構二叉樹，二叉樹中每個節點的值都不相同。

三、解題思路

  首先要知道二叉樹的前序周遊和中序周遊：

前序周遊： 根 左 右
  中序周遊： 左 根 右
           

  仔細觀察一波，可以發現從前序周遊序列中第一位就是目前子樹的根，而通過這個根，可以将中序周遊序列分成左右兩個子樹。根據這一特性，就可以完成二叉樹的遞歸建構。

四、代碼實作

const buildTree = (preorder, inorder) => {
  if (preorder.length === 0) {
    return null
  }
  const rv = preorder.shift()
  const root = new TreeNode(rv)
  const index = inorder.indexOf(rv)

  root.left = buildTree(preorder.slice(0, index), inorder.slice(0, index))
  root.right = buildTree(preorder.slice(index), inorder.slice(index + 1))

  return root
}
           

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

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

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