1028.从先序遍历还原二叉树

链接：1028.从先序遍历还原二叉树
难度：Hard
标签：树、深度优先搜索、字符串、二叉树
简介：我们从二叉树的根节点 root  开始进行深度优先搜索。在遍历中的每个节点处，我们输出  D  条短划线（其中  D  是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。如果节点只有一个子节点，那么保证该子节点为左子节点。给出遍历输出  S，还原树并返回其根节点  root。

题解 1 - typescript

• 编辑时间：2020-06-18
• 执行用时：148ms
• 内存消耗：43.1MB
• 编程语言：typescript
• 解法介绍：利用正则解析字符串，使用递归去深度获取节点，由于 leetcode 存在 Bug 无法在函数内 new TreeNode()，使用内建 TreeNode1 代替内部 TreeNode。

class TreeNode1 {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}
function recoverFromPreorder(S: string): TreeNode | null {
  const maxVal = 10 ** 9;
  const maxValLen = maxVal.toString().length;
  const maxValReg = `\d{1,${maxValLen}}`;
  const nextReg = (h: string): string => `${maxValReg}${h}${maxValReg}`;
  return getNode(S, 1);
  function getNode(nodeStr: string, level: number): TreeNode | null {
    // console.log("====");
    // console.log("nodeStr:" + nodeStr);
    // console.log("level:" + level);
    const nodeStrLen = nodeStr.length;
    if (nodeStrLen === 0) return null;
    const h = ''.padStart(level, '-');
    const reg = new RegExp(nextReg(h), 'g');
    // console.log(reg);
    const node = new TreeNode1(parseInt(nodeStr));
    const cache: { index: number; str: string }[] = [];
    let index = -1;
    let match: RegExpMatchArray | null = nodeStr.substr(index + 1).match(reg);
    while (match !== null) {
      // console.log(match);
      index = nodeStr.indexOf(match[0]);
      const str = match[0];
      cache.push({
        index,
        str,
      });
      const tempIndexH = str.indexOf('-');
      const newNodeStr = nodeStr.substr(index + tempIndexH + h.length);
      // console.log(str);
      match = newNodeStr.match(reg);
      // console.log(match);
    }
    // console.log(cache);
    for (let i = 0, len = cache.length; i < len; i++) {
      const { index, str } = cache[i];
      const indexH = str.indexOf(h);
      const newStr = nodeStr.substr(
        index + indexH + h.length,
        i === len - 1 ? nodeStrLen : cache[i + 1].index
      );
      if (node.left === null) {
        node.left = getNode(newStr, level + 1);
      } else {
        node.right = getNode(newStr, level + 1);
      }
    }
    return node;
  }
}