二叉树最大宽度

约 1807 字大约 6 分钟

2024-12-25

⭐️ 题目日期：

字节 - 2024/12/23

🌳 题目描述：

给定一棵二叉树的根节点 root，计算这棵树的所有层数中的最大宽度，其中，宽度是指这棵树的每层最左到最右的非空节点之间的距离，而它们之前出现的一些 null 节点，也算入距离之内。

示例 1：
输入：head = [10, 8, 15, 1, null, 13, null]
输出：3

解释图例：

🕵🏽 面试评估：

这道题主要考察候选人对 DFS（深度优先搜索）或 BFS（广度优先搜索）的理解与运用，以及能否对每一层的节点进行正确的标记与处理，从而结合遍历方式算出最大的宽度。以下的思路分析基于DFS。

🧗难度系数：

⭐️ ⭐️ ⭐️

📝思路分析：

题目要求计算这棵树的最大宽度，即最左节点到最右节点之间的距离加 1，如果我们能标记两个节点的索引，则索引的差值加 1，即为答案。

为了便于计算，我们可以规定：

左子节点的索引是父节点索引的 2 * index。
右子节点的索引是父节点索引的 2 * index + 1。

这样每一层的节点对应的索引都是递增的，且相邻节点索引的差值为 1。

那么我们就可以采用递归的方式（DFS）来遍历这棵树，并且每次都传递给每个节点其索引和深度。

在递归过程中，我们可以用一个 list 来记录每一层的最左节点的索引，list 的索引代表递归的深度，随后用最右节点的索引减去最左节点的索引，再加 1 来更新最大的宽度。

以案例为例，图解如下

首先我们从树的根节点开始，每个节点都会被赋予一个“索引”和“深度”。
接着开始递归，每当进入一个节点，我们都先判断该层是否已经记录这一层最左边节点的索引，如果没有，则当前节点为该层的最左节点，随后计算当前节点到当前层最左边节点的宽度。
1. 层 0（根节点层）：
  - 当前节点是根节点 10，深度是 0，索引是 0
  - 因为这是树的第一层，我们将 list[0] = 0，表示根节点 10 是该层的最左节点
  - 接着递归他的左右子树
  - 层 1：
    - 进入左子树节点 8，深度是 1，索引为 0。此时，list[1] = 0，表示节点 8 是该层的最左节点
    - 随后递归他的左右子树
      - 层 2：
        进入节点 8 的左子树节点 1，深度是 2，索引为 0。此时，list[2] = 0，表示节点 1 是该层的最左节点
        当前节点到当前层的最左节点的距离为 levelWidth：0 - 0 + 1 = 1，这里更新目前发现的最大距离 1
        节点 8 没有右子树，回溯处理节点 10
    - 计算节点 10 到当前层的最左节点的距离为 levelWidth： 0 - list[1] + 1 = 0 - 0 + 1 = 1，没有大于当前存储的最大值，无需更新 result[0]
    - 随后回溯处理节点 10 的右子树
    - 进入右子树节点 15，深度为 1，索引为 1，list.size() <= depth, 为 false, 说明当前层的最左节点已经找到。
    - 随后递归他的左右子树
      - 层 2：
        进入节点 15 的左子树 13，深度为 2，索引为 2，因为该层已经有一个最左节点（节点 1），所以不会更新 list[2]。
        当前节点到当前层的最左节点的距离为 levelWidth： 2 - list[2] + 1 = 2 - 0 + 1 = 3，此时更新最大宽度 result[0] = 3。
        节点 15 的右子树为空，回溯到节点 15。
    - 计算节点 15 到当前层最左节点的距离为 levelWidth： 1 - list[1] + 1 = 1 - 0 + 1 = 2，没有大于当前存储的最大值，无需更新 result[0]
    - 随后回溯到根节点，计算节点到当前层的最左节点距离为 levelWidth： 0 - list[0] + 1 = 0 - 0 + 1 = 1，没有大于当前存储的最大值，无需更新result[0]
所以最终值为：3

💻代码（Java、Python、C++）：

Java

 public int widthOfBinaryTree(TreeNode root) {
        // 从根节点开始递归，最开始深度为 0，索引为 0
        int[] result = {0};
        dfs(root, 0, 0, new ArrayList<>(), result);
        return result[0];
    }

    public void dfs(TreeNode node, int depth, int index, List<Integer> list, int[] result) {
        // 如果节点为空返回
        if (node == null) {
            return;
        }

        // 若列表里面还没有加入最左节点，说明当前的节点就是该层的最左节点
        if (list.size() <= depth) {
            list.add(index);
        }

        // 递归左子树
        dfs(node.left, depth + 1, index * 2, list, result);
        // 递归右子树
        dfs(node.right, depth + 1, index * 2 + 1, list, result);

        // 当前节点到当前层最左节点的宽度 = 当前节点的索引 - 当前层级最左节点的索引 + 1
        int levelWidth = index - list.get(depth) + 1;

        // 更新最大的宽度
        if (levelWidth > result[0]) {
            result[0] = levelWidth;
        }
    }

Python

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # 从根节点开始递归，最开始深度为 0，索引为 0
        result = [0]
        self.dfs(root, 0, 0, [], result)
        return result[0]
    
    def dfs(self, node: Optional[TreeNode], depth: int, index: int, list: list[int], result: list[int]) -> None:
        # 如果节点为空返回
        if not node:
            return
        
        # 若列表里面还没有加入最左节点，说明当前的节点就是该层的最左节点
        if len(list) <= depth:
            list.append(index)
        
        # 递归左子树
        self.dfs(node.left, depth + 1, index * 2, list, result)
        # 递归右子树
        self.dfs(node.right, depth + 1, index * 2 + 1, list, result)
        
        # 当前节点到当前层最左节点的宽度 = 当前节点的索引 - 当前层级最左节点的索引 + 1
        levelWidth = index - list[depth] + 1
        
        # 更新最大的宽度
        result[0] = max(result[0], levelWidth)

C++

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        int result = 0;
        vector<unsigned long long> list;
        // 从根节点开始递归，最开始深度为 0，索引为 0
        dfs(root, 0, 0, list, result);
        return result;
    }

private:
    void dfs(TreeNode* node, unsigned long long depth, unsigned long long index,
             vector<unsigned long long>& list, int& result) {
        // 如果节点为空，直接返回
        if (node == nullptr) {
            return;
        }

        // 若列表里面还没有加入最左节点，说明当前的节点就是该层的最左节点
        if (list.size() <= depth) {
            list.push_back(index);
        }

        // 递归左子树
        dfs(node->left, depth + 1, index * 2, list, result);
        // 递归右子树
        dfs(node->right, depth + 1, index * 2 + 1, list, result);

        // 当前节点到当前层最左节点的宽度 = 当前节点的索引 - 当前层级最左节点的索引 + 1
        int levelWidth = index - list[depth] + 1;

        // 更新最大宽度
        result = max(result, levelWidth);
    }
};

🚵🏻复杂度分析：

时间复杂度：O(n)，n 为树中节点的数量，因为每个节点遍历一次。

空间复杂度：O(h)，h 为树的高度；空间的使用来自于 list 对树的每一层最左边节点的位置的存储 O(h) 以及深度优先递归栈的调用 (同为 O(h))。若树为完全二叉树，高度为 logn，最坏情况（当树处于不平衡状态，形如链表状）树的高度为 n。

🔬在线评测(Online Judge):

题目链接