2023-06-08：给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。
将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，
这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
输入：root = [1,3,2,5,3,null,9]。
输出：4。
答案 2023-06-09：
大体步骤如下：
该算法使用一个容器来存储节点的信息，每个节点信息包含节点本身和其在满二叉树中的位置。
1.如果 root 为空，返回 0，否则初始化一个变量 ans 来记录最大宽度。
2.使用一个队列 queue 来存储节点信息，将根节点的信息{root,1}加入队列。
3.循环处理队列，每次处理一层，对于每个节点：
a.pop 出队列中的节点信息，将该节点作为当前节点 cur。
b.如果当前节点是该层的第一个节点，则记录其 Index 为 left。
c.如果当前节点是该层的最后一个节点，则记录其 Index 为 right。
d.如果当前节点有左孩子，则将其左孩子信息{cur.Node.Left,cur.Index*2}加入队列。
e.如果当前节点有右孩子，则将其右孩子信息{cur.Node.Right,cur.Index*2+1}加入队列。
4.计算当前层的宽度，将其记录为 max(right-left+1,ans)。
5.返回最大宽度 ans。
时间复杂度：每个节点仅仅入队、出队各一次，因此时间复杂度为 O(N)，其中 N 为树中节点的数量。
空间复杂度：本算法使用了一个队列来存储节点信息，队列中的节点数量不会超过两层的节点数，因此空间复杂度为 O(2^h)，其中 h 为树的高度。如果是完全二叉树，h=logN，空间复杂度为 O(N)。
golang 完整代码如下：
package main
import ( "container/list" "fmt")
type TreeNode struct { Val int Left *TreeNode Right *TreeNode}
type Info struct { Node *TreeNode Index int}
func widthOfBinaryTree(root *TreeNode) int { if root == nil { return 0 }
var ans, left, right int queue := list.New() queue.PushBack(&Info{Node: root, Index: 1}) for queue.Len() > 0 { size := queue.Len() for i := 0; i < size; i++ { cur := queue.Front().Value.(*Info) queue.Remove(queue.Front()) if i == 0 { left = cur.Index } if i == size-1 { right = cur.Index } if cur.Node.Left != nil { queue.PushBack(&Info{Node: cur.Node.Left, Index: cur.Index * 2}) } if cur.Node.Right != nil { queue.PushBack(&Info{Node: cur.Node.Right, Index: cur.Index*2 + 1}) } } ans = max(ans, right-left+1) } return ans}
func max(a, b int) int { if a > b { return a } return b}
func main() { root := &TreeNode{ Val: 1, Left: &TreeNode{ Val: 3, Left: &TreeNode{ Val: 5, }, }, Right: &TreeNode{ Val: 2, Right: &TreeNode{ Val: 3, Right: &TreeNode{ Val: 9, }, }, }, } fmt.Println(widthOfBinaryTree(root))}
复制代码
c++完整代码如下：
#include <iostream>#include <queue>
using namespace std;
struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}};
struct Info { TreeNode* node; int index; Info(TreeNode* n, int i) : node(n), index(i) {};};
int widthOfBinaryTree(TreeNode* root) { if (!root) { return 0; } int ans = 1; int leftmost_idx, rightmost_idx;
queue<Info> q; q.push(Info(root, 1));
while (!q.empty()) { int level_size = q.size(); leftmost_idx = q.front().index, rightmost_idx = q.front().index;
for (int i = 0; i < level_size; i++) { Info cur = q.front(); q.pop();
leftmost_idx = min(leftmost_idx, cur.index); rightmost_idx = max(rightmost_idx, cur.index);
if (cur.node->left) { q.push(Info(cur.node->left, cur.index << 1)); } if (cur.node->right) { q.push(Info(cur.node->right, (cur.index << 1) | 1)); } }
ans = max(ans, rightmost_idx - leftmost_idx + 1); }
return ans;}
int main() { TreeNode* root = new TreeNode(1); root->left = new TreeNode(3); root->right = new TreeNode(2); root->left->left = new TreeNode(5); root->left->right = nullptr; root->right->left = new TreeNode(3); root->right->right = new TreeNode(9);
cout << widthOfBinaryTree(root) << endl;
return 0;}
复制代码
c 语言完整代码如下：
#include <stdio.h>#include <stdlib.h>#include <limits.h>
struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right;};
struct TreeNode* newTreeNode() { struct TreeNode* ans = (struct TreeNode*)malloc(sizeof(struct TreeNode)); ans->val = 0; ans->left = NULL; ans->right = NULL; return ans;};
struct Info { struct TreeNode* node; int index;};
int widthOfBinaryTree(struct TreeNode* root) { if (!root) { return 0; } int ans = 1; int leftmost_idx, rightmost_idx;
struct Info init = { root, 1 }; struct Info cur; struct TreeNode* node; struct Info* q = newTreeNode(); int head = 0, tail = 0; q[head++] = init;
while (head != tail) { int level_size = head - tail; leftmost_idx = q[tail].index, rightmost_idx = q[tail].index;
for (int i = 0; i < level_size; i++) { cur = q[tail++];
leftmost_idx = leftmost_idx < cur.index ? leftmost_idx : cur.index; rightmost_idx = rightmost_idx > cur.index ? rightmost_idx : cur.index;
node = cur.node; if (node->left) { q = (struct Info*)realloc(q, sizeof(struct Info) * (head + 1)); q[head++] = (struct Info){ node->left, cur.index << 1 }; } if (node->right) { q = (struct Info*)realloc(q, sizeof(struct Info) * (head + 1)); q[head++] = (struct Info){ node->right, (cur.index << 1) | 1 }; } }
ans = max(ans, rightmost_idx - leftmost_idx + 1); }
free(q);
return ans;}
int main() { struct TreeNode* root = newTreeNode(); root->val = 1; root->left = newTreeNode(); root->left->val = 3; root->right = newTreeNode(); root->right->val = 2; root->left->left = newTreeNode(); root->left->left->val = 5; root->left->right = NULL; root->right->left = newTreeNode(); root->right->left->val = 3; root->right->right = newTreeNode(); root->right->right->val = 9;
printf("%d\n", widthOfBinaryTree(root));
free(root->left->left); free(root->left); free(root->right->left); free(root->right->right); free(root->right); free(root);
return 0;}
复制代码
评论