常数时间内插入删除、获得随机数

设计一个支持在平均 时间复杂度 O(1)O(1) 下，执行以下操作的数据结构。

insert(val)：当元素 val 不存在时，向集合中插入该项。 remove(val)：元素 val 存在时，从集合中移除该项。 getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例

// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

方法一 Array + Object(Map)

思路

使用动态数组存储元素值，对象存储值到索引的映射；有索引可以实现常数时间的 insert 和 getRandom。remove 的常数时间则使用：总是删除最后一个元素，将要删除元素和最后一个元素交换，然后将最后一个元素删除来实现。

详解

1. insert: 添加元素到动态数组, 并在对象中添加值到索引的映射关系。
2. remove: 在对象中查找要删除元素的索引，将要删除元素与最后一个元素交换，删除最后一个元素，更新对象中的对应关系。
3. getRandom: 借助 random 函数，获取下标范围内的整数，然后取出数组对应下标元素。

/**
 * Initialize your data structure here.
 */
const RandomizedSet = function () {
  this.arr = [];
  this.values = {};
};

/**
 * Inserts a value to the set. Returns true if the set did not already contain the specified element.
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function (val) {
  if (this.values[val] >= 0) {
    return false;
  } else {
    this.values[val] = this.arr.length;
    this.arr.push(val);
    return true;
  }
};

/**
 * Removes a value from the set. Returns true if the set contained the specified element.
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function (val) {
  const i = this.values[val];
  const l = this.arr.length;
  if (i >= 0) {
    this.values[this.arr[l - 1]] = i;
    this.values[val] = -1;
    this.arr.splice(i, 1, this.arr[l - 1]);
    this.arr.pop();
    return true;
  } else {
    return false;
  }
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function () {
  const l = this.arr.length;
  const i = Math.floor(Math.random() * l);
  return this.arr[i];
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

复杂度分析

• 时间复杂度：O(1)O(1)

  getRandom 时间复杂度为 O(1)O(1)，insert 和 remove 平均时间复杂度为 O(1)O(1)

• 空间复杂度：O(n)O(n)

  存储了 n 个元素信息

中序遍历二叉树、从前序与中序遍历序列构造二叉树和二叉搜索树中第 K 小的元素

中序遍历二叉树

给定一个二叉树，返回它的中序遍历。

示例

输入: [1,null,2,3]
树结构:
TreeNode: {
  val: 1,
  right: {
    val: 2,
    right: null,
    left: {
      val: 3,
      right: null,
      left: null,
    },
  },
  left: null
}
图解:
   1
    \
     2
    /
   3
输出: [1,3,2]

方法一 递归算法

思路

对于查询一棵二叉树的所有子节点，由于其层级深且多，使用递归是最直接的方法，加上题目需要中序遍历的条件，我们需要查询完根节点后，将左侧的子节点全部查询出来，递归方法能帮助我们一直查询子节点下是否还有子节点，查询到处于左边的子节点时，插入结果数组，直到查到所有的节点的左侧节点之后，再查询右侧节点，这样查询就实现了中序遍历二叉树。

详解

1. 传入根节点，查询根节点的值插入结果数组，并且查询根节点是否存在左子节点
2. 存在左子节点，将该节点作为参数重新传入递归函数，并将其值插入结果数组
3. 递归函数将会把步骤1和2重复进行，直到当前左边的所有节点都插入了结果数组
4. 当前最左边的子节点都查询完毕后，之前的右子节点也将作为参数重新传入递归函数
5. 此时递归函数还是会先从传入的节点的左边开始查询，直到步骤1和2重复查询到没有左边的子节点为止
6. 所有的右子节点的左子节点也查询结束后，再次查询该节点的右子节点，如此重复直到所有节点查询结束即完成查询

const inorderTraversal = (root) => {
  const result = [];
  const middleSequence = (root) => {
    if (!root) return;
    const { left, right, val } = root;
    left && middleSequence(left);
    val && result.push(val);
    right && middleSequence(right);
  };
  middleSequence(root);
  return result;
};

复杂度分析

• 时间复杂度：O(n)O(n)

  递归函数 T(n) = 2*T(n/2)+1T(n)=2∗T(n/2)+1 ，因此时间复杂度为 O(n)O(n)

• 空间复杂度：O(logn)O(logn)

方法二 迭代算法

思路

迭代算法的思路比较巧妙，结合之前的递归算法，我们知道了要一直先查询左边的节点，那我们不如先将所有的左边的子节点存下来，通过类似堆栈的方式，将左边的子节点都插入一个临时的数组，直到所有的左边子节点都查询完后，我们再将其从临时数组中按插入顺序的倒序移除，即后进先出，并将其值插入结果数组，所有左子节点查询完后，右节点再重复一样的操作，即可实现中序遍历二叉树。

详解

1. 声明一个临时数组，传入根节点，并查询该根节点的左子节点并将下一次的迭代对象赋值为该节点，同时插入临时数组
2. 左节点传入迭代函数后，将重复步骤1，一直到查询不到左子节点为止
3. 当第一次传入的左子节点和其以下的所有左子节点被查询完后，迭代的对象会变成undefined
4. 此时我们开始处理这段时间插入的所有左子节点，此时增加一个判断条件，临时数组里是否存在未处理的节点
5. 将最后插入的子节点，也是最深层的子节点的值插入结果数组，并移除出临时数组，再将该节点的右节点作为下一次迭代对象
6. 查询该节点下的所有左子节点，重复步骤1和2，直到查询结束为止，再重复步骤3和4，一直往树的根节点查询，直到结束

const inorderTraversal = (root) => {
  const result = [];
  const stack = [];
  let node = root;
  while (node || stack.length > 0) {
    if (node) {
      stack.push(node);
      node = node.left;
      continue;
    }
    node = stack.pop();
    result.push(node.val);
    node = node.right;
  }
  return result;
};

复杂度分析

• 时间复杂度：O(n)O(n)

  查询所有节点需要O(n)O(n)的时间

• 空间复杂度：O(n)O(n)

  创建了长度为n的数组。

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

根据一棵树的前序遍历与中序遍历构造二叉树。

可假设树中没有重复的元素。

示例

给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树
    3
   / \
  9  20
    /  \
   15   7

名词解释

前序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

示例解析：二叉树的前序遍历先访问根结点为3，然后遍历左子树9，最后遍历右子树；右子树为一棵树，先访问根结点为20，再遍历左子树为15，最后遍历右子树为7。则示例中二叉树的前序遍历为[3，9，20，15，7]。

中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。

示例解析：二叉树的中序遍历，先遍历左子树为9，然后访问根结点3，最后遍历右子树；右子树为一棵树，先遍历左子树为15，再访问根结点为20，最后遍历右子树为7。则示例中二叉树的中序遍历为[9，3，15，20，7]。

方法一 递归法

思路

前序遍历中首先出现的结点均为根结点，结合中序遍历中对应结点及距离上（下）一结点的中间的数字可确定此结点的左（右）子树中的结点值，在左（右）子树中的结点值确定后，再结合前序遍历的数组可得出左（右）子树的根结点，再根据中序遍历中的左（右）子树的根结点得出左（右）子树的左右子树……如此递归，则可得出完整的二叉树。

根据题目中的例子，前序遍历首先出现的数（即3）为根结点，3 在中序遍历中的位置之前的结点 9 必定为根结点的左子树；在前序遍历中 9 之后的结点为根结点的右子树；同样的方法确定前序遍历中的 20 为右子树的根结点，15 为右子树的左结点，7 为右子树的右结点。

详解

1. 根据前序遍历数组找到该树的根结点；

const root = preorder[preStart];

preorder 为前序遍历的数组，preStart 为前序遍历数组的下标。初始化时置为 0，为二叉树的根结点；之后每次递归均为该子树的根结点的下标。

2. 若中序遍历中根结点的位置之前有值，则证明该根结点有左子树，然后从第一步开始递归，拿到该根结点的左子树；

// 存在左子树
  if (inOrderIndex - inStart >= 1) {
    rootNode.left = constructNewNode(preorder, inorder, preStart + 1, preStart + (inOrderIndex - inStart), inStart, inOrderIndex - 1);
  }

3. 若中序遍历中根结点的位置之后有值，则证明该根结点有右子树，然后从第一步开始递归，拿到该根结点的右子树

//存在右子树
  if (inLength - inOrderIndex >= 1) {
    rootNode.right = constructNewNode(preorder, inorder, preStart + (inOrderIndex - inStart) + 1, preLength, inOrderIndex + 1, inLength);
  }

代码

function TreeNode (val) {
  this.val = val;
  this.left = this.right = null;
}

function buildTree (preorder, inorder) {
  if (preorder.length === 0 || inorder.length === 0) {
    return null;
  }
  return constructNewNode(preorder, inorder, 0, preorder.length, 0, inorder.length);
}

function findInorderIndex (list, target) {
  if (list.length === 0) {
    return undefined;
  }

  let index;
  list.forEach((item, i) => {
    if (item === target) {
      index = i;
    }
  });
  return index;
}

function constructNewNode (preorder, inorder, preStart, preLength, inStart, inLength) {
  const root = preorder[preStart];
  const inOrderIndex = findInorderIndex(inorder, root);
  // 中序遍历根结点左边为左子树，右边为右子树
  const rootNode = new TreeNode(root);
  // 存在左子树
  if (inOrderIndex - inStart >= 1) {
    rootNode.left = constructNewNode(preorder, inorder, preStart + 1, preStart + (inOrderIndex - inStart), inStart, inOrderIndex - 1);
  }

  // 存在右子树
  if (inLength - inOrderIndex >= 1) {
    rootNode.right = constructNewNode(preorder, inorder, preStart + (inOrderIndex - inStart) + 1, preLength, inOrderIndex + 1, inLength);
  }
  return (root || root === 0) ? rootNode : null;
}

复杂度分析

• 时间复杂度：O(n)O(n)

  由于每次递归 inorder 和 preorder 的总数都会减 1，因此需要递归 nn 次，故时间复杂度为 O(n)O(n)，其中 nn 为结点个数

• 空间复杂度：O(n)O(n)

  所用空间与树本身存储空间正相关

方法二 遍历法

思路

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]

借用了栈的数据结构，先将根结点放入，然后前序遍历数组，若在中序遍历的节点与前序遍历的节点相等（即找到了已遍历节点的右子树的根结点）则从匹配到的节点到该根节点出栈。如此，遍历完前序数组后则可唯一确定一颗完整的二叉树。【重点在于判断何时找到了右子树的根节点，在中序遍历中的节点与前序遍历的当前节点相等时则可确定，原因在于前序遍历中遍历到右子树的根结点且与中序遍历中的节点相等时，必然可以确定匹配节点的左子节点已经遍历完毕；同时确定该子树是哪个根结点的右子树（示例解析中已说明），问题即可得到解决】

示例解析：

若当前需要确定的二叉树为示例所示：

    3
   / \
  9  20
    /  \
   15   7

首先，假设只有前序遍历的数组preorder = [3,9,20,15,7]，需要确定上面的唯一一颗二叉树，可以做什么？

我们首先可以确定这颗树的根结点为【3】，然后是节点【9】，按照前序遍历的原则，先遍历根结点，再遍历左子节点，然后再遍历右子节点，可以确定的是【9】是【3】的子树的根结点，但是无法确定是左子树的根结点，还是右子树的根结点；

此时需要结合中序遍历的数组inorder = [9,3,15,20,7]来进行判断。可以先假设【9】是【3】的右子树的根结点，根据中序遍历的特点，先遍历左子树，再访问根结点，再遍历右子树可得出中序遍历的顺序为[3,9]，与既定的中序遍历数组的顺序不苻，所以可确定【9】是【3】的左子树的根结点；

同时，注意到了此时的前序遍历的【9】和中序遍历的【9】相等了，说明【9】是没有左子节点的，从中序遍历的特点以及【9】在中序遍历中所处的位置可以得出。则前序遍历的下一个节点必定是【20】必定为右子树的根结点，那么【20】是【3】的右子树的根结点，还是【9】的右子树的根结点呢？

假设【20】是【3】的右子树的根结点，那么中序遍历的数组顺序应当是[9,3,20]；假设【20】是【9】的右子树的根结点，那么中序遍历的数组顺序应当是[9,20,3]；由此可确定【20】是【3】的右子树的根结点。

此时我们的中序遍历的数组是[9,3,15,20,7]，【9】匹配，【3】匹配，最后一次匹配是【3】，所以【20】是【3】的右子树。

    3
   / \
  9  20
    /  \
   15   7

综上所述，可用一个栈来记录已经遍历过的节点，遍历前序遍历的数组，作为当前节点的左子树的根结点，直到前序遍历的当前节点与中序遍历的节点相匹配，即找到了遍历过的某个节点的右子树的根结点，则从该匹配节点到最后一个匹配节点出栈，并将当前节点作为最后一个匹配节点的右子树的根结点。如此，将前序与中序数组遍历完毕，便可确定唯一的一颗二叉树。

详解

1、根据前序遍历确定该树的根结点，将其放入栈中；

treeNodeList.push(root);

2、进行前序遍历，若中序遍历中当前值为正好为栈中最后一个根结点时，该根结点出栈，当前前序遍历的结点为该根结点的右子根结点；否则当前前序遍历的结点为该根结点的左子根结点，并将当前值放入栈中，继续遍历，重复第二个步骤。

代码

function TreeNode (val) {
  this.val = val;
  this.left = this.right = null;
}

const buildTree = function (preorder, inorder) {
  if (preorder.length === 0) {
    return null;
  }
  const treeNodeList = [];
  const root = new TreeNode(preorder[0]);
  treeNodeList.push(root);
  // j从0开始，为中序遍历的序数
  let j = 0;
  for (let i = 1; i < preorder.length; i++) {
    const current = new TreeNode(preorder[i]);
    let curParent;

    // 中序遍历至当前根结点时，右子树根结点确定，当前根结点出栈
    while (treeNodeList.length !== 0 && treeNodeList[treeNodeList.length - 1].val === inorder[j]) {
      curParent = treeNodeList[treeNodeList.length - 1];
      treeNodeList.length--;
      j++;
    }
    if (curParent) {
      curParent.right = current;
    } else {
      treeNodeList[treeNodeList.length - 1].left = current;
    }
    treeNodeList.push(current);
  }
  return root;
};

复杂度分析

• 时间复杂度：O(n)O(n)

  前序遍历与中序遍历的序数变动基本一致

• 空间复杂度：O(n)O(n)

  所用空间与二叉树的左子树的深度正相关为 O(\log_2{n})O(log2n)，树本身存储空间为 O(n)O(n)，取大者

二叉搜索树中第 K 小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1：

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

示例 2：

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 3

进阶： 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

方法一 递归查找

根据二叉搜索树的特性：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

思路

我们只需要中序遍历输入的树，然后输出第 k 个元素即可以得到第 k 个最小的元素。最简单的办法就是写一个递归函数进行遍历然后将遍历结果保存到数组中。

详解

中序遍历的原则是：先遍历左子树，然后访问根节点，最后遍历右边子树，当发现已经找到第 k 个元素，提前中止遍历

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
const kthSmallest = function (root, k) {
  const result = [];

  function travel (node) {
    // 当已经找到 k 个元素时提前中止遍历
    if (result.length >= k) return;
    if (node.left) {
      // 遍历左子树
      travel(node.left);
    }
    // 保存根节点
    result.push(node.val);
    if (node.right) {
      // 遍历右子树
      travel(node.right);
    }
  }
  travel(root);
  return result[k - 1];
};

复杂度分析

• 时间复杂度：O(n)O(n)

  时间复杂度与节点个数相关，nn 个节点最多需要递归查找 nn 次，所以时间复杂度为 O(n)O(n)。

• 空间复杂度：O(n)O(n)

  空间复杂度与调用堆栈有关，调用栈需要记住每个节点的值，所以空间复杂度为 O(n)。

方法二 循环查找

思路

还是一样采用中序遍历，只不过我们不使用递归，改为循环的方式实现

详解

见代码注释

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
const kthSmallest = function (root, k) {
  const result = []; let current = root; const stack = [];
  while (result.length < k && (current || stack.length > 0)) {
    if (current) {
      // 有左孩子，表示有比当前元素更小的，继续查找
      if (current.left) {
        // 把当前节点暂存到堆栈
        stack.push(current);
        // 继续查找左子树
        current = current.left;
      } else {
        // 没有左孩子表示当前元素是目前最小，存入数组
        result.push(current.val);
        // 左子树查找完后开始查找右子树
        current = current.right;
      }
    } else {
      // 已经遍历到叶子节点，需要回溯，从节点堆栈中弹出一个节点
      current = stack.pop();
      // 由于左子树已经查找完成，那么当前节点是目前最小的节点
      result.push(current.val);
      // 然后继续查找右子树
      current = current.right;
    }
  }
  return result[k - 1];
};

复杂度分析

• 时间复杂度：O(n)O(n)

  时间复杂度与节点个数相关，nn 个节点最多需要循环查找 nn 次，所以时间复杂度为 O(n)O(n)。

• 空间复杂度：O(n)O(n)

  由于需要一个需要辅助栈来记住节点的值，最坏情况下所有节点都会存进辅助栈，所以空间复杂度为 O(n)O(n)。