Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
restores a binary tree from a string containing positive integers (representing nodes) separated by dashes (representing branches) (e.g. in: "1-2--3--4-5--6--7", out: [1,2,5,3,4,6,7]
//* Definition for a binary tree node.
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
/**
* @param {string} S
* @return {TreeNode}
*/
class ParentStack {
constructor() {
this.length = 0
this.head = null
}
push(val) {
const node = new ParentNode(val)
if (!this.head) {
this.head = node
} else {
node.next = this.head
this.head = node
}
this.length++
}
pop() {
const node = this.head
this.head = this.head.next
this.length--
return node.val
}
peek() {
if (this.head) {
return this.head.val
} else {
return null
}
}
}
class ParentNode {
constructor(val) {
this.val = val
this.next = null
}
}
var recoverFromPreorder = function(S) {
var root
const DASH = '-'
const parentStack = new ParentStack()
let i = 0
while (i < S.length) {
let char = S[i]
let dashCount = 0
// count dashes
while (char === DASH && i < S.length) {
dashCount++
i++
char = S[i]
}
// get all digits for int
let charString = ''
// check next chars until dash is found again
while (char >= 0 && char < 10) { // check if char is a number
charString = charString + char
// check next char
i++
char = S[i]
}
// if dash count is greater than parent stack length, throw error
if (dashCount > parentStack.length) {
throw new Error('invalid input')
}
// pop parents to match dash count
while (parentStack.length &&
parentStack.length - dashCount > 0) {
parentStack.pop()
}
// charString should be all digits for integer
// next char will be dash now
// make tree node from next index val
let treeNode = new TreeNode(charString)
// node = parent stack peek
const parent = parentStack.peek()
// if dash count is 0
// and parent stack length is 0
// make root for parent stack
if (dashCount === 0 &&
parentStack.length === 0) {
root = new TreeNode(charString)
parentStack.push(root)
// if node's left has not been assigned
} else if (!parent.left) {
// add as node's left
parent.left = treeNode
// push to parent stack
parentStack.push(treeNode)
} else if (!parent.right) {
// else if node's right has not been assigned
// add as node's right
parent.right = treeNode
// push to parent stack
parentStack.push(treeNode)
} else {
// else this parent has all nodes, check others
parentStack.pop()
i++
continue
}
}
return root
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.