手写算法：二叉树的垂序遍历

987. 二叉树的垂序遍历

理解题意

1. 二叉树的根节点为(0, 0), 左子树节点为(row + 1, col - 1), 右子数节点为 (row + 1, col + 1)

2. 垂序遍历，其实是根据 col 值从上到下（数值小的拍在前面）进行排序，同行同列上，若有多个节点，则比较节点的数值大小。

解题思路

1. 前序遍历二叉树，用 col 作为 key 创建 Map 对象， 记录节点的 row 和 val 值。将同一列的节点，塞入同一个数组内。

2. 遍历 Map 对象，对数组中的内容进行排序

3. 再根据顺序依次推入 result 数组中

代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalTraversal = function(root) {
  let map = new Map();
  let result = [];
  const dfs = (node, row, col) => {
    if (node === null) return 0;

    map.set(col, [
      {
        val: node.val,
        row
      },
      ...(map.get(col) || [])
    ]);

    dfs(node.left, row + 1, col - 1);
    dfs(node.right, row + 1, col + 1);
  };
  dfs(root, 0, 0);

  for (const [key, values] of map.entries()) {
    // 将节点进行排序，同行同列比较大小，其他的从上到下排序
    values.sort((a, b) => {
      if (a.row === b.row) {
        return a.val - b.val;
      }
      return a.row - b.row;
    });

    // key为col，正数时，越往下越大，负数则相反
    if (key >= 0) {
      result.push(values.map(item => item.val));
    } else {
      result.unshift(values.map(item => item.val));
    }
  }
  return result;
};

手写题：实现 DOM2JSON 函数

请实现 DOM2JSON 函数，可以把一个 DOM 节点输出成 JSON 的格式

dom2Json

const dom2Json = (node = this) => {
  const obj = {
    nodeType: node.nodeType
  };

  // 有tagName拿tagName，不然拿nodeName
  if (node.tagName) {
    obj.tagName = node.tagName;
  } else if (node.nodeName) {
    obj.nodeName = node.nodeName;
  }

  // text、comment、CDATA节点会返回文本内容，其他则返回null
  if (node.nodeValue) {
    obj.nodeValue = node.nodeValue;
  }

  const attributes = node.attributes;
  const childNodes = node.childNodes;
  let arr, length;

  if (attributes) {
    length = attributes.length;
    arr = obj.attributes = new Array(length);

    for (let i = 0; i < length; i++) {
      const attr = attributes[i];
      arr[i] = [attr.nodeName, attr.nodeValue];
    }
  }

  if (childNodes) {
    length = childNodes.length;
    arr = obj.childNodes = new Array(length);

    for (let i = 0; i < length; i++) {
      arr[i] = dom2Json(childNodes[i]);
    }
  }
  return obj;
};

json2Dom

const json2Dom = obj => {
  if (typeof obj === 'string') {
    obj = JSON.parse(obj);
  }
  let node;
  const nodeType = obj.nodeType;

  switch (nodeType) {
    // ELEMENT_NODE 创建元素节点
    case 1:
      node = document.createElement(obj.tagName || obj.nodeName);
      const attributes = obj.attributes;
      for (let i = 0; i < attributes.length; i++) {
        const attr = attributes[i];
        // 设置属性名与值
        node.setAttribute(attr[0], attr[1]);
      }
      break;

    // 创建文本节点
    case 3:
      node = document.createTextNode(obj.nodeValue);
      break;

    // 创建注释节点
    case 8:
      node = document.createComment(obj.nodeValue);
      break;

    // 创建文档节点
    case 9:
      node = document.implementation.createDocument(null, null);
      break;

    // 创建文档类型节点
    case 10:
      node = document.implementation.createDocumentType(obj.tagName, '', '');
      break;

    // 创建文档碎片，是虚拟节点，不会被添加到文档中
    case 11:
      node = document.createDocumentFragment();
      break;

    default:
      // 未知的返回null
      return null;
  }

  // 如果类型为元素节点或文档碎片节点
  if (nodeType === 1 || nodeType === 11) {
    const childNodes = obj.childNodes;
    for (let i = 0; i < childNodes.length; i++) {
      node.appendChild(json2Dom(childNodes[i]));
    }
  }
  return node;
};