Last active
April 15, 2019 17:21
-
-
Save SCollinA/b5988efd81708575c7882b5a4ba1c23c to your computer and use it in GitHub Desktop.
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]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//* 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