/**
* 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();
};