【一天一大 lee】从中序与后序遍历序列构造二叉树 (难度:中等)-Day20200925

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

    3
   / \
  9  20
    /  \
   15   7

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} inorder  中序遍历
 * @param {number[]} postorder 后序遍历
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
  let rootIndex = postorder.length - 1,
    map = new Map()
  // 记录在中序遍历数组中每个节点的位置，方便在得到根节点时查找左右子树节点
  for (let i = 0; i < inorder.length; i++) {
    map.set(inorder[i], i)
  }
  function dfs(leftIndex, rightIndex) {
    if (leftIndex > rightIndex) return null
    let root = new TreeNode(postorder[rootIndex]),
      i = map.get(postorder[rootIndex])
    rootIndex--
    root.right = dfs(i + 1, rightIndex)
    root.left = dfs(leftIndex, i - 1)
    return root
  }
  return dfs(0, inorder.length - 1)
}

var buildTree = function(inorder, postorder) {
  let rootIndex = postorder.length - 1,
    root = new TreeNode(postorder[rootIndex]),
    // 维护下一次遍历追击子树的最新子树
    queue = [root],
    inorderIndex = inorder.length - 1

  rootIndex--

  while (rootIndex >= 0) {
    let node = queue[queue.length - 1],
      nodeVal = postorder[rootIndex]
    // 不等于上一个生成子树的节点，则说明是上一个子树的右节点
    if (node.val !== inorder[inorderIndex]) {
      node.right = new TreeNode(nodeVal)
      queue.push(node.right)
    } else {
      // 维护inorder的倒序遍历索引跳过已经生成树的根节点
      while (
        queue.length &&
        queue[queue.length - 1].val === inorder[inorderIndex]
      ) {
        node = queue.pop()
        inorderIndex--
      }
      // 情况 2
      node.left = new TreeNode(nodeVal)
      queue.push(node.left)
    }

    rootIndex--
  }

  return root
}