/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {string} S
 * @return {TreeNode}
 */
const recoverFromPreorder = function (S) {
  let cur = 0, SLen = S.length, stack = [];
  while (cur < SLen) {
    let level = 0, val = '';
    // 处理数字和 "-" 符号, 数字存起来,记录符号的个数
    while (cur < SLen && S[cur] === '-') {
      level++;
      cur++;
    }
    while (cur < SLen && S[cur] !== '-') {
      val += S[cur];
      cur++;
    }
    // 栈的长度就代表着树的层数
    while (stack.length > level) {
      stack.pop();
    }
    const node = new TreeNode(val);
    // 构建树
    if (stack.length > 0) {
      if (stack[stack.length - 1].left === null) {
        stack[stack.length - 1].left = node;
      } else {
        stack[stack.length - 1].right = node;
      }
    }
    // 构建之后新的节点就又是新的一层, 所以把新节点 push 到栈里
    stack.push(node);
  }
  while (stack.length > 1) {
    stack.pop()
  };
  // 返回栈顶元素, 也就是根节点
  return stack.pop();
};