LeetCode Entry
1028. Recover a Tree From Preorder Traversal
Recover binary tree from depth-dashes string
1028. Recover a Tree From Preorder Traversal hard
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/903
Problem TLDR
Recover binary tree from depth-dashes string #hard #stack
Intuition
Go deeper until the current depth is bigger than the previous, otherwise pop up.
Recursion was a more mind-bending to write.
Approach
- Rust can’t resolve a type of the Vec until
push - c++ raw pointers are useful, for the Kotlin we have to resort to some wrapper to maintain the main pointer
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun recoverFromPreorder(t: String, pd: Int = -1, i: IntArray = intArrayOf(0)): TreeNode? {
var j = i[0]; var d = 0; while (j < t.length && t[j] == '-') { d++; j++ }
if (pd >= d) return null else i[0] = j
var v = 0; while (i[0] < t.length && t[i[0]] != '-') v = v * 10 + (t[i[0]++] - '0')
return TreeNode(v).apply { left = recoverFromPreorder(t, d, i); right = recoverFromPreorder(t, d, i) }
}
pub fn recover_from_preorder(t: String) -> Option<Rc<RefCell<TreeNode>>> {
let (mut i, mut q, mut f, t) = (0, vec![], vec![], t.as_bytes());
while i < t.len() {
let (mut d, mut v) = (0, 0); while t[i] == b'-' { d += 1; i += 1 }
while i < t.len() && t[i] != b'-' { v = v * 10 + (t[i] - b'0') as i32; i += 1 }
while q.last().is_some_and(|x| *x >= d) { q.pop(); f.pop(); };
let n = Some(Rc::new(RefCell::new(TreeNode::new(v)))); f.push(n.clone()); q.push(d); let l = f.len();
if let Some(mut p) = f.get_mut(l - 2).and_then(|x| x.as_mut()).map(|x| x.borrow_mut()) {
if p.left.is_none() { p.left = n.clone() } else { p.right = n.clone() }
}
}; f[0].clone()
}
TreeNode* recoverFromPreorder(string& t, int pd = -1, int* i = new int(0)) {
int d = 0, v = 0, j = *i; while (j < size(t) && t[j] == '-') d++, j++;
if (pd >= d) return nullptr; *i = j;
while (*i < size(t) && t[*i] != '-') v = v * 10 + t[(*i)++] - '0';
return new TreeNode(v, recoverFromPreorder(t, d, i), recoverFromPreorder(t, d, i));
}