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

LeetCode-105

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 【左右子树也是保持这个特性】
 * 前序遍历：根 左 右
 * 中序遍历：左 根 右
 */

// 【理解重点】
/**
 * 由前序遍历的特性可知：先根 - 在左 - 再右
 * 从前续遍历的头部开始取头部节点，然后的节点是属于左子树的头部节点，因此要先递归左子树】
*/
var buildTree = function(preorder, inorder) {
  // 从前序遍历中取出根
  let rootVal = preorder.shift() // 从头部开始取子树的根
  // 从中序遍历中得到index
  let index = inorder.findIndex(item => item === rootVal)
  // 从中序遍历中获取根val的左边arr(这个arr也是中序遍历的)
  let leftArr = inorder.slice(0, index)
  // 从中序遍历中获取根val的右边arr(这个arr也是中序遍历的)
  let rightArr = inorder.slice(index + 1)
  // 实例化根节点
  let root = new TreeNode(rootVal)

  // 如果左arr存在, 则递归左子树【先递归左子树：从前续遍历的头部开始取头部节点，然后的节点是属于左子树的头部节点，因此要先递归左子树】
  if(leftArr.length) root.left = buildTree(preorder, leftArr)
  // 如果右arr存在, 则递归右子树
  if(rightArr.length) root.right = buildTree(preorder, rightArr)

  // 返回树
  return root
}