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

#include

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 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

#include

#include

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;

}

文章链接

评论可见,请评论后查看内容,谢谢!!!评论后请刷新页面。