LeetCode Entry

515. Find Largest Value in Each Tree Row

25.12.2024 medium 2024 kotlin rust

Tree layers maxes

515. Find Largest Value in Each Tree Row medium blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/843

Problem TLDR

Tree layers maxes #medium

Intuition

Do DFS or BFS

Approach

• 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;
    }