[Leetcode 662]- Maximum Width of Binary Tree (2023/04/20)

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.

 

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

Maximum Width of Binary Tree - LeetCode

 

Constraints: 

• The number of nodes in the tree is in the range [1, 3000].
• -100 <= Node.val <= 100

 

Hint 1

노드의 개수가 최대 3000개이므로, 충분히 brute force 방식으로 접근가능하다.

 

Hint 2

각 레벨중 최대 너비를 구하는게 목표이므로 BFS로 접근 시 용이하다.

 

Hint 3

특정 레벨에 대해, 너비는, 우측 노드의 인덱스 - 좌측 노드의 인덱스 + 1이다.

 

Hint 4

부모 노드에 대해, 좌측 노드의 인덱스는 2*(부모의 인덱스) + 1 , 우측 노드의 인덱스는 2*(부모의 인덱스) + 2

 

Approach (** 테스트 케이스 중 maxSafeInteger의 범위를 넘는 인덱스가 있기에, 인덱스 계산이 bigInt를 사용했습니다**)

1. queue에는 [node,  idx , lv] 이렇게 3가지 정보를 저장한다.

var widthOfBinaryTree = function(root) {
    
    if(!root.left && !root.right){
        return 1;
    }
    let lvList = []
    let prevLv = 0;
    let leftMost = 0n;
    let rightMost = 0n;
    const queue = [[root ,0n , 0]];
};

2. prevLv가 lv과 달라지는 시점이 바로, 특정 레벨 구간에 대한 탐색이 끝났단 의미이다. rightMost - leftMost + 1 이 곧 너비이다.  leftMost를 해당 시점의 노드 인덱스로 갱신한다.

 

    while(queue.length > 0){
        const [root, idx ,lv] = queue.shift();
        
        if(lv !== prevLv){
            prevLv = lv;
            lvList.push(rightMost - leftMost +1n);
            leftMost = idx;
        }
    }

 

3. 탐색을 진행하는 동안 rightMost값은 항상 현재 인덱스로 갱신한다.

    while(queue.length > 0){
        const [root, idx ,lv] = queue.shift();
        
        if(lv !== prevLv){
            prevLv = lv;
            lvList.push(rightMost - leftMost +1n);
            leftMost = idx;
        }
        rightMost = idx;
    }

 

 

Solution

var widthOfBinaryTree = function(root) {
    
    if(!root.left && !root.right){
        return 1;
    }
    let lvList = []
    let prevLv = 0;
    let leftMost = 0n;
    let rightMost = 0n;
    const queue = [[root ,0n , 0]];

    while(queue.length > 0){
        const [root, idx ,lv] = queue.shift();
        
        if(lv !== prevLv){
            prevLv = lv;
            lvList.push(rightMost - leftMost +1n);
            leftMost = idx;
        }
        rightMost = idx;
        if(root.left){
            queue.push([root.left , (2n*idx + 1n) , lv + 1]);
        }
        if(root.right){
            queue.push([root.right , (2n*idx + 2n)  , lv + 1]);
        }
    }
    lvList.push(rightMost - leftMost + 1n)
    lvList = lvList.map(Number)
    return Math.max(...lvList)
};