lambdas in c++ are interesting, don't forget to add &
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(log(n))$$
Code
fun largestValues(root: TreeNode?): List<Int> = buildList {
fun dfs(n: TreeNode?, d: Int): Unit = n?.run {
if (d < size) set(d, max(get(d), `val`)) else add(`val`)
dfs(left, d + 1); dfs(right, d + 1)
} ?: Unit
dfs(root, 0)
}
pub fn largest_values(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut res = vec![]; let Some(r) = root.clone() else { return res };
let mut q = VecDeque::from([r]);
while q.len() > 0 {
let mut max = i32::MIN;
for _ in 0..q.len() {
let n = q.pop_front().unwrap(); let n = n.borrow();
max = max.max(n.val);
if let Some(x) = n.left.clone() { q.push_back(x); }
if let Some(x) = n.right.clone() { q.push_back(x); }
}
res.push(max);
}; res
}
vector<int> largestValues(TreeNode* root) {
vector<int> r;
auto f = [&](this auto const& f, TreeNode* n, int d) -> void {
if (d < r.size()) r[d] = max(r[d], n->val); else r.push_back(n->val);
if (n->left) f(n->left, d + 1); if (n->right) f(n->right, d + 1);
}; if (root) f(root, 0); return r;
}
Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.
