我要招人

去企业版

首页 > 试题广场 >

二叉树的最大宽度

[编程题]二叉树的最大宽度

热度指数：1547 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树，你需要编写一个函数来获取这课树的最大宽度，二叉树的最大宽度是指具有节点数最多的那一层的结点个数。

示例1

输入

{1,2,3}

输出

示例2

输入

{1,2,3,4,5,#,6}

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Spectre_

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求这可树的最大宽度
     * @param head TreeNode类 树的根节点
     * @return int整型
     */
    int getMaxWidth(TreeNode* head) {
        // write code here
        // 时间复杂度O(N)，空间复杂度O(logN)
        int maxWidth = 0, size;
        if (head == nullptr) return maxWidth;
        queue<TreeNode*> que;
        que.emplace(head);
        while (!que.empty()) {
            size = que.size();
            maxWidth = maxWidth > size ? maxWidth : size;
            while (size--) {
                if (que.front()->left) que.emplace(que.front()->left);
                if (que.front()->right) que.emplace(que.front()->right);
                que.pop();
            }
        }
        return maxWidth;
    }
};

发表于 2021-10-06 19:32:51 回复(0)

Jsix

import java.util.*;

* public class TreeNode {

* int val = 0;

* TreeNode left = null;

* TreeNode right = null;

* public TreeNode(int val) {

* this.val = val;

* }

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* 求这可树的最大宽度

* @param head TreeNode类树的根节点

* @return int整型

public int getMaxWidth (TreeNode head) {

if (head == null) {

return 0;

}

Deque<TreeNode> dequeue = new ArrayDeque<>();

Map<TreeNode, Integer> map = new HashMap<>();

dequeue.add(head);

map.put(head, 1);

int level = 1;

int levelNodes = 0;

int maxWidth = Integer.MIN_VALUE;

while (!dequeue.isEmpty()) {

TreeNode node = dequeue.poll();

// 获取当前所在层

int curLevel = map.get(node);

if (level == curLevel) {

levelNodes++;

} else {

maxWidth = Math.max(maxWidth, levelNodes);

level++;

levelNodes = 1;

}

if (node.left != null) {

dequeue.add(node.left);

map.put(node.left, curLevel + 1);

}

if (node.right != null) {

dequeue.add(node.right);

map.put(node.right, curLevel + 1);

}

maxWidth = Math.max(maxWidth, levelNodes);

return maxWidth;

}

发表于 2023-09-25 15:54:11 回复(0)

C/C++

Jayna_Su

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求这可树的最大宽度
     * @param head TreeNode类 树的根节点
     * @return int整型
     */
    int cnt[100010];
    int max_depth = 0;
    int max_width = 0;
    void dfs(TreeNode* root, int depth)
    {
        if (!root) return;
        
        cnt[depth] ++;
        max_depth = max(max_depth, depth);
        if (root->left) dfs(root->left, depth + 1);
        if (root->right) dfs(root->right, depth + 1);
    }
    int getMaxWidth(TreeNode* root) {
        // write code here
        if (!root) return max_width;
        
        int depth = 0;
        dfs(root, depth);
        for (int i = 0; i <= max_depth; i ++)
            if (cnt[i] > max_width) max_width = cnt[i];
        
        return max_width;
    }
};

发表于 2022-11-12 18:26:03 回复(0)

尾上世莉架

class Solution {
public:
    int getMaxWidth(TreeNode* head) {
        // write code here
        if(!head) return 0;
        int maxwid = 0;
        int last = 0, first = 0;
        TreeNode* q[10000];
        int front = 0, rear = 0;
        q[rear++] = head;
        TreeNode* cur;
        while(rear>front){
            cur = q[front];
            if(cur->left) q[rear++] = cur->left;
            if(cur->right) q[rear++] = cur->right;
            if(front == last){
                maxwid = maxwid>(last-first+1)?maxwid:last-first+1;
                // 此时front为一层的最后一个
                first = front + 1;
                last = rear - 1;
            }
            front++;
        }
        return maxwid;
    }
};

发表于 2022-11-10 22:59:31 回复(0)