題目網址：https://leetcode.cn/problems/maximum-width-of-binary-tree/

題意：給一 BT 的 root, 返回該 tree 的最大寬度。

每一層的寬度被定義為兩個端點之間的長度（該層最左和最右的非空節點, 兩端點之間的 null 也計入長度）。

答案可用 32-bit 有號整數表示。

Solution 1：

想法：利用 DFS

我們可以 assign idx 給每個 node, 然後計算出每層的寬度

  • root = 1
  • left = 2 * parent
  • right = 2 * parent + 1

但是一旦遇到高度 > 64 的 skew tree, 32-bit 的有號整數便無法表達

➔ 因此紀錄每層最左邊的非空節點的 idx, 把它當作該層所有節點 idx 的 offset, 因此新的 idx 為原先 idx 扣掉該層的 offset, 然後再用新的 idx 來對 child 進行遞迴

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        res = 0;
        dfs(root, 0, 0);
        return res;
    }

private:
    long res;
    vector<long> left_most; // 紀錄每一層最左非空節點的 idx

    void dfs(TreeNode* node, long idx, int depth){
        if (!node) {
            return;
        }

        if (depth == left_most.size()) {
            left_most.emplace_back(idx);
        }

        res = max(res, idx - left_most[depth] + 1); // 維護最大寬度
        idx -= left_most[depth]; // 統一扣掉該層最左非空節點的 idx, 避免下面 * 2 超出 long
        dfs(node->left, 2 * idx, depth + 1);
        dfs(node->right, 2 * idx + 1, depth + 1);
    }
};
  • time：$O(n)$ ➔ 遍歷整個 BT
  • space：$O(n)$ ➔ 遞迴深度不超過 n

Solution 2：

想法：利用 BFS, 道理同 Solution 1, 一樣要記錄每層最左非空節點的 idx 並把它當成該層的 offset

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        int res = 0;
        queue<pair<TreeNode*, long>> q; // {node : idx}
        q.emplace(root, 0);

        while (!q.empty()) {
            const int n = q.size();
            const auto offset = q.front().second; // 該層最左非空節點的 idx
            res = max(res, static_cast<int>(q.back().second - offset + 1));  // 維護最大寬度

            for (int i = 0; i < n; ++i) {
                const auto [node, idx] = q.front();
                q.pop();

                // 統一扣掉該層最左非空節點的 idx, 避免下面 * 2 超出 long
                idx -= offset;

                if (node->left) {
                    q.emplace(node->left, 2 * idx);
                }

                if (node->right) {
                    q.emplace(node->right, 2 * idx + 1);
                }
            }
        }

        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷整個 BT
  • space：$O(n)$ ➔ q 中的元素不超過 n