介绍下深度优先遍历和广度优先遍历，如何实现？

• 深度优先遍历
  • 是指从某个顶点出发，首先访问这个顶点，然后找出刚访问这个结点的第一个未被访问的邻结点，然后再以此邻结点为顶点，继续找它的下一个顶点进行访问。重复此步骤，直至所有结点都被访问完为止。
• 广度优先遍历
  • 是从某个顶点出发，首先访问这个顶点，然后找出刚访问这个结点所有未被访问的邻结点，访问完后再访问这些结点中第一个邻结点的所有结点，重复此方法，直到所有结点都被访问完为止。

// 1.深度优先遍历的递归写法
function deepTraversal(node) {
  let nodes = [];
  if (node != null) {
    nodes.push[node];
    let children = node.children;
    for (let i = 0; i < children.length; i++) {
      deepTraversal(children[i]);
    }
  }
  return nodes;
}

// 2.深度优先遍历的非递归写法
function deepTraversal(node) {
  let nodes = [];
  if (node != null) {
    let stack = [];
    // 同来存放将来要访问的节点
    stack.push(node);
    while (stack.length !== 0) {
      let item = stack.pop();
      // 正在访问的节点
      nodes.push(item);
      let children = item.children;
      for (let i = children.length - 1; i >= 0; i--) {
        // 将现在访问点的节点的子节点存入stack，供将来访问
        stack.push(children[i]);
      }
    }
  }
  return nodes;
}

// 3.广度优先遍历的递归写法
function wideTraversal(node) {
  let nodes = [], i = 0;
  if (node != null) {
    nodes.push(node);
    wideTraversal(node.nextElementSibling);
    node = nodes[i++];
    wideTraversal(node.firstElementChild);
  }
  return nodes;
}

// 4.广度优先遍历的非递归写法
function wideTraversal(node) {
  let nodes = [], i = 0;
  while (node != null) {
    nodes.push(node);
    node = nodes[i++];
    let children = node.children;
    for (let i = 0; i < children.length; i++) {
      nodes.push(children[i]);
    }
  }
  return nodes;
}

深度遍历广度遍历的区别？

对于算法来说 无非就是时间换空间 空间换时间

• 1、深度优先不需要记住所有的节点, 所以占用空间小, 而广度优先需要先记录所有的节点占用空间大
• 2、深度优先有回溯的操作(没有路走了需要回头)所以相对而言时间会长一点
• 3、深度优先采用的是堆栈的形式, 即先进后出
• 4、广度优先则采用的是队列的形式, 即先进先出

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log(m+n))。

示例1： nums1 = [1, 3] nums2 = [2] 中位数是 2.0

示例2： nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3) / 2 = 2.5

const findMedianSortedArrays = function(nums1, nums2) {
  const lenN1 = nums1.length;
  const lenN2 = nums2.length;
  const median = Math.ceil((lenN1 + lenN2 + 1) / 2);
  const isOddLen = (lenN1 + lenN2) % 2 === 0;
  const result = new Array(median);
  let i = 0; // pointer for nums1
  let j = 0; // pointer for nums2
  for (let k = 0; k < median; k++) {
    if (i < lenN1 && j < lenN2) {
      if (nums1[i] < nums2[j]) {
        result[i + j] = nums1[i++];
      } else {
        result[i + j] = nums2[j++];
      }
    } else if (i < lenN1) {
      result[i + j] = nums1[i++];
    } else if (j < lenN2) {
      result[i + j] = nums2[j++];
    }
  }
  if (isOddLen) {
    return (result[median - 1] + result[median - 2]) / 2;
  } else {
    return result[median - 1];
  }
};

说出几种你能想到的JS 变量交换的方法

方法一：算术运算法

实现原理：