662

Posted on In , Views:

題目:
https://leetcode.com/problems/maximum-width-of-binary-tree/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#define MAXN 3005
using ll = unsigned long long;
// 測資72是超級skewed tree，深度可以達到2^3000，所以index要用unsigned long long存才不會超範圍

TreeNode* nodeq[MAXN];
ll indexq[MAXN];

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        ll ans = 1;
        int l = 0, r = 0;
        nodeq[r] = root;
        indexq[r++] = 1;

        while(l < r){
            ans = max(ans, indexq[r-1] - indexq[l] + 1);
            int size = r-l;
            for(int i=0; i<size; ++i){
                TreeNode* curr = nodeq[l];
                ll id = indexq[l++];
                if(curr->left != nullptr){
                    nodeq[r] = curr->left;
                    indexq[r++] = id*2;
                }
                if(curr->right != nullptr){
                    nodeq[r] = curr->right;
                    indexq[r++] = id*2+1;
                }
            }
        }
        return ans;
    }
};