首页 > 试题广场 >

二叉树的最大宽度

[编程题]二叉树的最大宽度
  • 热度指数:1539 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个二叉树,你需要编写一个函数来获取这课树的最大宽度,二叉树的最大宽度是指具有节点数最多的那一层的结点个数。

示例1

输入

{1,2,3}

输出

2
示例2

输入

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

输出

3

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
/**
 * 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)
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)
/**
 * 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)