深圳南山区网站建设公司,企业做网站的优势,网站建设创意,表白网址链接制作文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
广度优先搜索
二【题目难度】
中等
三【题目编号】
662.二叉树最大宽度
四【题目描述】
给… 文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】
广度优先搜索
二【题目难度】
中等
三【题目编号】
662.二叉树最大宽度
四【题目描述】
给你一棵二叉树的根节点 root 返回树的 最大宽度 。树的 最大宽度 是所有层中最大的 宽度 。每一层的 宽度 被定义为该层最左和最右的非空节点即两个端点之间的长度。将这个二叉树视作与满二叉树结构相同两端点间会出现一些延伸到这一层的 null 节点这些 null 节点也计入长度。题目数据保证答案将会在 32 位 带符号整数范围内。
五【题目示例】 示例 1 输入root [1,3,2,5,3,null,9]输出4解释最大宽度出现在树的第 3 层宽度为 4 (5,3,null,9) 。 示例 2 输入root [1,3,2,5,null,null,9,6,null,7]输出7解释最大宽度出现在树的第 4 层宽度为 7 (6,null,null,null,null,null,7) 。 示例 3 输入root [1,3,2,5]输出2解释最大宽度出现在树的第 2 层宽度为 2 (3,2) 。
六【题目提示】
树中节点的数目范围是 [1, 3000]100 Node.val 100
七【解题思路】
其实这道题就是二叉树的层序遍历的变种值得注意的是需要利用完全二叉树的性质 在完全二叉树中可以将其节点存储到数组中并且对于序号为i的节点节点编号从1开始其 左子节点的序号为i * 2右子节点的序号为i * 2 1 利用以上性质我们可以将每一层的二叉树的节点编号用编号值计算每一层的宽度当计算出每一层的宽度后就可以计算得到整个二叉树的最大宽度 具体细节请参考下面的代码
八【时间频度】
时间复杂度 O ( n ) O(n) O(n) n n n为传入的二叉树的节点个数空间复杂度 O ( n ) O(n) O(n) n n n为传入的二叉树的节点个数
九【代码实现】
Java语言版
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/class Solution {public int widthOfBinaryTree(TreeNode root) {// 最小宽度为1int res 1;// 初始化队列queue用于存储当前层节点ListPairTreeNode, Integer queue new ArrayListPairTreeNode, Integer();queue.add(new PairTreeNode, Integer(root, 1));// 使用广度优先遍历算法计算二叉树的最大高度while (!queue.isEmpty()) {// temp用于存储下一层节点ListPairTreeNode, Integer temp new ArrayListPairTreeNode, Integer();for (PairTreeNode, Integer pair : queue) {TreeNode node pair.getKey();int index pair.getValue();if (node.left ! null) {temp.add(new PairTreeNode, Integer(node.left, index * 2));}if (node.right ! null) {temp.add(new PairTreeNode, Integer(node.right, index * 2 1));}}// 计算二叉树的最大宽度res Math.max(res, queue.get(queue.size() - 1).getValue() - queue.get(0).getValue() 1);queue temp;}// 返回结果return res;}
}Python语言版
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right rightclass Solution:def widthOfBinaryTree(self, root: Optional[TreeNode]) - int:# 最小宽度为1res 1# 初始化队列queue用于存储当前层节点queue [[root, 1]]# 使用广度优先遍历算法计算二叉树的最大高度while queue:# temp用于存储下一层节点temp []for node, index in queue:if node.left:temp.append([node.left, index * 2])if node.right:temp.append([node.right, index * 2 1])# 计算二叉树的最大宽度res max(res, queue[-1][1] - queue[0][1] 1)queue temp# 返回结果return resC语言版
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/// 节点最多3000个
#define MAX_NODE_SIZE 3000// 比较大小
#define MAX(a, b) ((a) (b) ? (a) : (b));// 利用完全二叉树的性质存储二叉树node保留了节点的左右子树的关系index记录节点在数组中的位置索引
typedef struct
{struct TreeNode* node;unsigned long long index;
} levelNode;int widthOfBinaryTree(struct TreeNode* root)
{// 最小宽度为1unsigned long long res 1;// 初始化队列queue用于存储当前层节点temp用于存储下一层节点levelNode* queue (levelNode*)malloc(sizeof(levelNode) * MAX_NODE_SIZE);levelNode* temp (levelNode*)malloc(sizeof(levelNode) * MAX_NODE_SIZE);int queueSize 0;int tempSize 0;// 根节点入队列queue[queueSize].node root;queue[queueSize].index 1LL;// 使用广度优先遍历算法计算二叉树的最大宽度while (queueSize 0){// 将当前节点的所有下一层节点按照完全二叉树的索引值存储tempSize 0;for (int i 0; i queueSize; i){if (queue[i].node-left){temp[tempSize].node queue[i].node-left;temp[tempSize].index queue[i].index * 2;}if (queue[i].node-right){temp[tempSize].node queue[i].node-right;temp[tempSize].index queue[i].index * 2 1;} }// 计算二叉树的最大宽度res MAX(res, queue[queueSize - 1].index - queue[0].index 1);// 将存储当前层节点信息的队列重新赋值为存储好的下一层节点的信息队列queueSize tempSize;levelNode* change queue;queue temp;temp change;}// 返回结果return res;
}十【提交结果】 Java语言版 Python语言版 C语言版
