515. Find Largest Value in Each Tree Row

leetcode medium

#array#csharp#graph#leetcode#math#medium#queue#search#string#tree#two-pointers

Task

Дан корень двоичного дерева, верните массив наибольших значений в каждой строке дерева (индексация с 0).

Пример:

Input: root = [1,3,2,5,3,null,9]

Output: [1,3,9]

C# solution

matched/original

public class Solution {
    public IList<int> LargestValues(TreeNode root) {
        if (root == null) return new List<int>();
        
        var ans = new List<int>();
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        
        while (queue.Count > 0) {
            int currentLength = queue.Count;
            int currMax = int.MinValue;
            
            for (int i = 0; i < currentLength; i++) {
                var node = queue.Dequeue();
                currMax = Math.Max(currMax, node.val);
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            
            ans.Add(currMax);
        }
        
        return ans;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int> LargestValues(TreeNode root) {
        if (root == null) return new List<int>();
        
        var ans = new List<int>();
        var queue = new queue<TreeNode>();
        queue.Enqueue(root);
        
        while (queue.size() > 0) {
            int currentLength = queue.size();
            int currMax = int.MinValue;
            
            for (int i = 0; i < currentLength; i++) {
                var node = queue.Dequeue();
                currMax = max(currMax, node.val);
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            
            ans.push_back(currMax);
        }
        
        return ans;
    }
}

Java solution

matched/original

import java.util.*;

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        if (root == null) return Collections.emptyList();
        
        List<Integer> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int currentLength = queue.size();
            int currMax = Integer.MIN_VALUE;
            
            for (int i = 0; i < currentLength; i++) {
                TreeNode node = queue.poll();
                currMax = Math.max(currMax, node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
            ans.add(currMax);
        }
        
        return ans;
    }
}

JavaScript solution

matched/original

var largestValues = function(root) {
    if (!root) return [];
    
    const ans = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const currentLength = queue.length;
        let currMax = -Infinity;
        
        for (let i = 0; i < currentLength; i++) {
            const node = queue.shift();
            currMax = Math.max(currMax, node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        ans.push(currMax);
    }
    
    return ans;
};

Python solution

matched/original

from collections import deque
from typing import List, Optional

class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        ans = []
        queue = deque([root])
        
        while queue:
            current_length = len(queue)
            curr_max = float("-inf")
            
            for _ in range(current_length):
                node = queue.popleft()
                curr_max = max(curr_max, node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            ans.append(curr_max)
        
        return ans

Go solution

matched/original

func largestValues(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    
    ans := []int{}
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        currentLength := len(queue)
        currMax := math.MinInt64
        
        for i := 0; i < currentLength; i++ {
            node := queue[0]
            queue = queue[1:]
            if node.Val > currMax {
                currMax = node.Val
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        
        ans = append(ans, currMax)
    }
    
    return ans
}

Explanation

Algorithm

Если корень дерева равен null (пустое дерево), верните пустой список. Инициализируйте список ans для хранения результатов и очередь с корнем дерева для выполнения поиска в ширину (BFS).

Выполните BFS, пока очередь не пуста: инициализируйте currMax минимальным значением и сохраните длину очереди в currentLength. Повторите currentLength раз: удалите узел из очереди, обновите currMax, если значение узла больше. Для каждого дочернего узла, если он не равен null, добавьте его в очередь.

Добавьте currMax в ans. Верните ans.

😎