662. Maximum Width of Binary Tree

LeetCode medium оригинал: C# #bit-manipulation #csharp #leetcode #math #medium #queue #tree #two-pointers

LeetCode Static

Дан корень бинарного дерева, верните максимальную ширину данного дерева.

Максимальная ширина дерева - это максимальная ширина среди всех уровней.

Ширина одного уровня определяется как расстояние между конечными узлами (самыми левыми и самыми правыми ненулевыми узлами), где нулевые узлы между конечными узлами, которые присутствовали бы в полном бинарном дереве, продолжающемся до этого уровня, также учитываются при вычислении длины.

Гарантируется, что ответ будет в диапазоне 32-битного знакового целого числа.

Пример

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

Output: 4

Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

C# решение

сопоставлено/оригинал

using System;
using System.Collections.Generic;
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class Solution {
    public int WidthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        
        int maxWidth = 0;
        Queue<(TreeNode node, int pos)> queue = new Queue<(TreeNode, int)>();
        queue.Enqueue((root, 0));
        
        while (queue.Count > 0) {
            int levelSize = queue.Count;
            int firstPos = queue.Peek().pos;
            for (int i = 0; i < levelSize; i++) {
                var (node, pos) = queue.Dequeue();
                if (node.left != null) queue.Enqueue((node.left, 2 * pos));
                if (node.right != null) queue.Enqueue((node.right, 2 * pos + 1));
            }
            maxWidth = Math.Max(maxWidth, queue.Peek().pos - firstPos + 1);
        }
        
        return maxWidth;
    }
}

C++ решение

auto-draft, проверить перед отправкой

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
class Solution {
public:
    public int WidthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        
        int maxWidth = 0;
        queue<(TreeNode node, int pos)> queue = new queue<(TreeNode, int)>();
        queue.Enqueue((root, 0));
        
        while (queue.size() > 0) {
            int levelSize = queue.size();
            int firstPos = queue.Peek().pos;
            for (int i = 0; i < levelSize; i++) {
                var (node, pos) = queue.Dequeue();
                if (node.left != null) queue.Enqueue((node.left, 2 * pos));
                if (node.right != null) queue.Enqueue((node.right, 2 * pos + 1));
            }
            maxWidth = max(maxWidth, queue.Peek().pos - firstPos + 1);
        }
        
        return maxWidth;
    }
}

Java решение

auto-draft, проверить перед отправкой

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class Solution {
    public int WidthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        
        int maxWidth = 0;
        Queue<(TreeNode node, int pos)> queue = new LinkedList<(TreeNode, int)>();
        queue.Enqueue((root, 0));
        
        while (queue.size() > 0) {
            int levelSize = queue.size();
            int firstPos = queue.peek().pos;
            for (int i = 0; i < levelSize; i++) {
                var (node, pos) = queue.poll();
                if (node.left != null) queue.Enqueue((node.left, 2 * pos));
                if (node.right != null) queue.Enqueue((node.right, 2 * pos + 1));
            }
            maxWidth = Math.max(maxWidth, queue.peek().pos - firstPos + 1);
        }
        
        return maxWidth;
    }
}

JavaScript решение

сопоставлено/оригинал

var widthOfBinaryTree = function(root) {
    if (!root) return 0;

    let maxWidth = 0;
    const queue = [{ node: root, pos: 0 }];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const firstPos = queue[0].pos;
        for (let i = 0; i < levelSize; i++) {
            const { node, pos } = queue.shift();
            if (node.left) queue.push({ node: node.left, pos: 2 * pos });
            if (node.right) queue.push({ node: node.right, pos: 2 * pos + 1 });
        }
        const lastPos = queue[queue.length - 1]?.pos || firstPos;
        maxWidth = Math.max(maxWidth, lastPos - firstPos + 1);
    }

    return maxWidth;
};

Python решение

сопоставлено/оригинал

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        max_width = 0
        queue = deque([(root, 0)])
        
        while queue:
            level_length = len(queue)
            _, first_pos = queue[0]
            for i in range(level_length):
                node, pos = queue.popleft()
                if node.left:
                    queue.append((node.left, 2 * pos))
                if node.right:
                    queue.append((node.right, 2 * pos + 1))
            max_width = max(max_width, pos - first_pos + 1)
        
        return max_width

Algorithm

1⃣Инициализация:

Создайте очередь для хранения узлов и их позиций на уровне.

Начните с корневого узла и его позиции 0.

2⃣Обработка каждого уровня:

Для каждого уровня дерева получите его узлы и их позиции.

Вычислите ширину уровня как разницу между максимальной и минимальной позициями плюс один.

3⃣Обновление максимальной ширины:

Обновите максимальную ширину, если текущая ширина уровня больше.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.