LeetCode题解：105. 从前序与中序遍历序列构造二叉树，Simple O(n) without map，JavaScript，详细注释

[chencl1986]

原题连接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

解题思路：

1. 参考了Simple O(n) without map。
2. 我们可以用如下代码，打印出递归经过的所有路径：

var buildTree = function (preorder, inorder) {
  let preorderIndex = 0;
  let inorderIndex = 0;
  let preMap = new Map();
  let preRealMap = new Map();

  function build(direction, stop) {
    const item = {inorderIndex, stop: inorder.indexOf(stop), direction};
    preMap.has(preorderIndex)
      ? preMap.get(preorderIndex).push(item)
      : preMap.set(preorderIndex, [item]);

    if (inorder[inorderIndex] === stop) {
      return null;
    }

    preRealMap.has(preorderIndex)
      ? preRealMap.get(preorderIndex).push([0,1,2]\n[1,0,2])
      : preRealMap.set(preorderIndex, [item]);

    const root = new TreeNode(preorder[preorderIndex++]);

    root.left = build('left', root.val);
    inorderIndex++;
    root.right = build('right', stop);

    return root;
  }
  const res = build('root');
  console.log('preMap', preMap);
  console.log('preRealMap', preRealMap);

  return res;
};

3. 先考虑这样一个二叉树：

	      0
	    /   \
	   1     2

前序遍历：[0,1,2]
中序遍历：[1,0,2]

打印结果如下：

preMap Map(4) {
  0 => [
    { inorderIndex: 0, stop: -1, direction: 'root'}
  ],
  1 => [
    { inorderIndex: 0, stop: 1, direction: 'left' }
  ],
  2 => [
    { inorderIndex: 0, stop: 0, direction: 'left' },
    { inorderIndex: 1, stop: 1, direction: 'right' },
    { inorderIndex: 2, stop: -1, direction: 'right' }
  ],
  3 => [
    { inorderIndex: 2, stop: 2, direction: 'left' },
    { inorderIndex: 3, stop: -1, direction: 'right' }
  ]
}

preRealMap Map(3) {
  0 => [ { inorderIndex: 0, stop: -1, direction: 'root' } ],
  1 => [ { inorderIndex: 0, stop: 1, direction: 'left' } ],
  2 => [ { inorderIndex: 2, stop: -1, direction: 'right' } ]
}

4. 以及这样一个二叉树：

	      0
	    /   \
	   1     2
	  / \   / \ 
	 3   4 5   6

前序遍历：[0,1,3,4,2,5,6]
中序遍历：[3,1,4,0,5,2,6]

打印结果如下：

preMap Map(8) {
  0 => [ { inorderIndex: 0, stop: -1, direction: 'root' } ],
  1 => [ { inorderIndex: 0, stop: 3, direction: 'left' } ],
  2 => [ { inorderIndex: 0, stop: 1, direction: 'left' } ],
  3 => [
    { inorderIndex: 0, stop: 0, direction: 'left' },
    { inorderIndex: 1, stop: 1, direction: 'right' },
    { inorderIndex: 2, stop: 3, direction: 'right' }
  ],
  4 => [
    { inorderIndex: 2, stop: 2, direction: 'left' },
    { inorderIndex: 3, stop: 3, direction: 'right' },
    { inorderIndex: 4, stop: -1, direction: 'right' }
  ],
  5 => [ { inorderIndex: 4, stop: 5, direction: 'left' } ],
  6 => [
    { inorderIndex: 4, stop: 4, direction: 'left' },
    { inorderIndex: 5, stop: 5, direction: 'right' },
    { inorderIndex: 6, stop: -1, direction: 'right' }
  ],
  7 => [
    { inorderIndex: 6, stop: 6, direction: 'left' },
    { inorderIndex: 7, stop: -1, direction: 'right' }
  ]
}

preRealMap Map(7) {
  0 => [ { inorderIndex: 0, stop: -1, direction: 'root' } ],
  1 => [ { inorderIndex: 0, stop: 3, direction: 'left' } ],
  2 => [ { inorderIndex: 0, stop: 1, direction: 'left' } ],
  3 => [ { inorderIndex: 2, stop: 3, direction: 'right' } ],
  4 => [ { inorderIndex: 4, stop: -1, direction: 'right' } ],
  5 => [ { inorderIndex: 4, stop: 5, direction: 'left' } ],
  6 => [ { inorderIndex: 6, stop: -1, direction: 'right' } ]
}

5. 一前序遍历：[0,1,2]说明，这个解法有以下特点：

   • 始终用前序遍历来创建根节点和左子节点。
   • 将创建节点的值传入左子节点的递归，这样就标记了这个节点已被创建过。
   • 将stop的值传入右子节点的递归，是因为右子节点的递归会运行在左子节点的递归之后，也就是它必须判断它上一次递归创建节点的值。
   • 当左子节点的递归走到preorder的0和1位置时，此时它们两个节点肯定都没有被创建过，因此可以被正常创建节点，并且1会被链接到0的左子节点上。
   • 当右子节点的递归走到0、1时，0、1位置都已被创建过节点，会退出递归。
   • 只有在右子节点的递归走到2时，此时preorder[2]还未被创建过节点，此时会被创建并链接到右子节点。
   • 不断重复上面的过程，就可以保证左右节点都被连接到正确位置。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
/*
 */
var buildTree = function (preorder, inorder) {
  /**
   * @description 通过不断移动前、中序遍历的索引，生成二叉树
   * @param {number} stop // 停止递归的值
   * @return {TreeNode}
   */
  let preorderIndex = 0; // 前序遍历的索引指针
  let inorderIndex = 0; // 中序遍历的索引指针

  function build(
    stop // 已生成节点的值
  ) {
    // 如果当前中序遍历对应的值已被生成过节点，则无需重复生成
    if (inorder[inorderIndex] === stop) {
      return null;
    }

    // 使用谦虚遍历的值创建一个节点，同时将指针向前移动一位
    const root = new TreeNode(preorder[preorderIndex++]);

    // 标记当前值已被生成过节点，继续向左子节点递归
    root.left = build(root.val);
    // 中序遍历指针向前移动，不断查找可以生成右子节点的值
    inorderIndex++;
    // 将上层递归的结点值传入右子节点的递归，标记其已生成过节点
    root.right = build(stop);

    // 将当前生成好的节点返回到上一层递归，供连接到根节点
    return root;
  }

  return build();
};