Độ rộng tối đa của cây nhị phân trong C++

Cho cây nhị phân, tìm độ rộng tối đa của cây. Độ rộng của một cấp là khoảng cách giữa nút ngoài cùng bên trái và bên phải (kể cả các nút null giữa chúng). Cây được coi có cấu trúc như cây đầy đủ nhưng một số nút là null. Ví dụ: cây có độ rộng tối đa 4 tại cấp cuối với các nút [5,3,null,9].

Giải thuật

• ans := 1, hàng đợi đôi q lưu cặp (node, value).
• Đưa (root, 1) vào q.
• Khi q không rỗng:
  • size := q.size()
  • Nếu size == 1: đưa (q.front().first, 1) vào q, xóa phần tử đầu.
  • Khi size-- > 0:
    • curr := q.front(), xóa đầu.
    • Nếu curr.first->left tồn tại: đưa (left, 2*curr.second) vào q.
    • Nếu curr.first->right tồn tại: đưa (right, 2*curr.second+1) vào q.
  • Nếu q.size() > 1: ans = max(ans, q.back().second - q.front().second + 1).
• Trả về ans.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = NULL; right = NULL; }
};

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        deque<pair<TreeNode*, int>> q;
        q.push_back({root, 1});
        int ans = 1;
        while (!q.empty()) {
            int sz = q.size();
            if (sz == 1) {
                q.push_back({q.front().first, 1});
                q.pop_front();
            }
            while (sz--) {
                auto curr = q.front(); q.pop_front();
                if (curr.first->left)
                    q.push_back({curr.first->left, 2 * curr.second});
                if (curr.first->right)
                    q.push_back({curr.first->right, 2 * curr.second + 1});
            }
            if (q.size() > 1)
                ans = max(ans, q.back().second - q.front().second + 1);
        }
        return ans;
    }
};

Đầu vào

[1,3,2,5,3,null,9]

Đầu ra

4