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

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;};

	      0	    /   \	   1     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' } ]}

	      0	    /   \	   1     2	  / \   / \ 	 3   4 5   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' } ]}

/** * 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();};