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

LeetCode-106

/**
 * 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(inorder, postorder) {
  // 从后序遍历中取出根
  let rootVal = postorder.pop() // 从头部开始取子树的根
  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(rightArr.length) root.right = buildTree(rightArr, postorder)
  // 如果左arr存在, 则递归左子树
  if(leftArr.length) root.left = buildTree(leftArr, postorder)

  // 返回树
  return root
}