[Leetcode] 662. Maximum Width of Binary Tree

문제

Given the root of a binary tree, return the maximum width of the given tree.
The maximum width of a tree is the maximum width among all levels.
The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.
It is guaranteed that the answer will in the range of a 32-bit signed integer.
 
Example 1:

Input: root = [1,3,2,5,3,null,9] Output: 4 Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).
Example 2:

Input: root = [1,3,2,5,null,null,9,6,null,7] Output: 7 Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).
Example 3:

Input: root = [1,3,2,5] Output: 2 Explanation: The maximum width exists in the second level with length 2 (3,2).
 
Constraints:
The number of nodes in the tree is in the range [1, 3000].-100 <= Node.val <= 100

 

풀이

한 레벨의 노드 수를 구하는 일반적인 문제와 다르게, 이 문제는 같은 레벨 사이에 숨겨진 null 노드의 수도 고려해야한다.

어렵게 느껴질 수 도 있지만 tree array에서 i의 left child= 2*i+1, right child = 2*i+2 개념과 bfs를 활용하면 쉽게 풀 수 있다.

 

하지만 tree node에는 index position(pos)이 없기에 따로 structure을 만들어 저장했다. 

 

pos를 저장하기 위해 struct을 추가하고 enqueue() 를 새로 만든것을 제외하면 

일반적인 bfs와 풀이방식은 같다.

 

코드

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// need to track index in root array
// left child = 2*i+1, right = 2*i+2

typedef struct Node {
    struct TreeNode* left;
    struct TreeNode* right;
    long long pos;
} Node;

Node* createNode(struct TreeNode* root, int position) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->left = root->left;
    node->right = root->right;
    node->pos = position;

    return node;
}

void freeALL(Node** queue, int rear) {
    for(int i=0; i<rear; i++){
        free(queue[i]);
    }
    free(queue);
}

int widthOfBinaryTree(struct TreeNode* root) {
    Node** queue = (Node**)malloc(3001 * sizeof(Node*));
    int front=0, rear=0;
    long long frontpos=0, lastpos=0; // prevent overflow

    queue[rear++] = createNode(root, 0);
    int maxwidth = 0;

    while(front < rear) {
        int levelSize = rear-front;
        frontpos = -1;

        for(int i=0; i<levelSize; i++) {
            struct Node* curr = queue[front++];
            if(frontpos==-1) frontpos = curr->pos;
            lastpos = curr->pos;
            
            if(curr->left) queue[rear++] = createNode(curr->left, lastpos*2+1);
            if(curr->right) queue[rear++] = createNode(curr->right, lastpos*2+2);
        }
        maxwidth = ((lastpos-frontpos+1) > maxwidth)? (lastpos-frontpos+1) : maxwidth;
    }
    freeALL(queue, rear); 
    return maxwidth;
}