3 min read leetcode

662. Maximum Width of Binary Tree

662. Maximum Width of Binary Tree
Photo by Markus Spiske / Unsplash

題目連結: 662. Maximum Width of Binary Tree

題目描述

給定一個二元樹，請找出其最大寬度。

二元樹的寬度定義為任一層中，最左邊與最右邊的非空節點之間的節點數量（包含最左和最右的節點）。如果某一層只有一個節點，則該層的寬度為 1。

注意：答案不需要是連續的節點，只要計算同一層最左與最右非空節點之間的節點數量即可。

限制條件

  • 樹中節點的數量範圍是 [1, 3000]。
  • -100 <= Node.val <= 100

解題思路

我們需要計算二元樹的最大寬度。為了達到這個目標，可以使用廣度優先搜尋（BFS），逐層遍歷二元樹，同時為每個節點指定一個位置索引，以便計算該層的寬度。

主要概念

  • 廣度優先搜尋（BFS）：
    • 使用隊列（queue）進行層序遍歷。
    • 在遍歷每一層時，記錄該層的節點索引，計算該層的寬度。
  • 節點位置索引：
    • 將根節點的索引設為 1。
    • 對於每個節點：
      • 左子節點的索引為 2 * index。
      • 右子節點的索引為 2 * index + 1。
    • 這種索引方式類似於滿二元樹的陣列表示法。

步驟詳述

  1. 初始化：
    • 如果根節點為空，返回寬度 0。
    • 使用隊列 queue 來存儲節點和其對應的索引。
    • 將根節點和索引 1 加入隊列。
  2. 層序遍歷：
    • 當隊列不為空時，對每一層進行以下操作：
      • 記錄當前層的節點數量 n。
      • 記錄當前層第一個節點的索引 start 和最後一個節點的索引 end。
      • 計算當前層的寬度為 end - start + 1，並更新最大寬度 ans。
      • 遍歷當前層的所有節點：
        • 從隊列中取出節點和索引。
        • 將索引標準化，減去 start，以防止整數溢位。
        • 將左子節點和索引 2 * idx + 1 加入隊列。
        • 將右子節點和索引 2 * idx + 2 加入隊列。

注意事項

  • 防止整數溢位：
    • 由於節點的索引值可能非常大，應使用 unsigned long long 型別。
    • 在每一層，將索引值減去該層第一個節點的索引，進行標準化，防止索引值過大。

程式碼

/**
 * Definition for a binary tree node.
 * 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) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) {
            return 0;
        }

        int ans = 1;
        queue<pair<TreeNode*, unsigned>> q;
        q.push({ root, 1 });

        while (!q.empty()) {
            int n = q.size();

            ans = max(ans, (int)(q.back().second - q.front().second + 1));

            while (n--) {
                auto [node, num] = q.front();
                q.pop();
                if (node->left) {
                    q.push({ node->left, num << 1 });
                }
                if (node->right) {
                    q.push({ node->right, (num << 1) | 1 });
                }
            }
        }
        return ans;
    }
};

時間與空間複雜度分析

  • 時間複雜度：O(n)
    • 我們需要遍歷每個節點一次，因此時間複雜度為線性。
  • 空間複雜度：O(n)
    • 最壞情況下，隊列需要存儲整個樹的一層節點數量，空間複雜度為線性。

Justin