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

题目

我们从二叉树的根节点 root 开始进行深度优先搜索。

在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。

如果节点只有一个子节点，那么保证该子节点为左子节点。

给出遍历输出 S，还原树并返回其根节点 root。

题解

迭代

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {string} S
 * @return {TreeNode}
 */
var recoverFromPreorder = function(S) {
  let path = [];
  let pos = 0;
  while (pos < S.length) {
    // 获取当前节点的深度
    let level = 0;
    while (S[pos] == "-") {
      ++level;
      ++pos;
    }

    // 获取当前节点的值
    let val = 0;
    while (pos < S.length && !isNaN(S[pos])) {
      val = val * 10 + (S[pos] - "0");
      ++pos;
    }

    let node = new TreeNode(val);
    /* 两种情况 */
    // 节点是根节点的左子节点
    if (level == path.length) {
      if (path.length) {
        path[path.length - 1].left = node;
      }
    }
    // 节点是某一节点的右子节点
    else {
      while (level != path.length) {
        path.pop();
      }
      path[path.length - 1].right = node;
    }
    path.push(node);
  }
  return path[0];
};