社区首页 >专栏 >2023-06-08：给你一棵二叉树的根节点 root ，返回树的最大宽度。树的最大宽度是所有层中最大的宽度。每

2023-06-08：给你一棵二叉树的根节点 root ，返回树的最大宽度。树的最大宽度是所有层中最大的宽度。每

福大大架构师每日一题

发布于 2023-06-09 02:50:41

23400

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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