662. Maximum Width of Binary Tree / TypeScript

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).

 

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

 

 

풀이

function widthOfBinaryTree(root: TreeNode | null): number {
    let positions: number[] = [0];
    let width: number = 0;

    function dfs(node: TreeNode | null, level: number, position: number) {
        if(!node) return;
        if(positions[level] === undefined) positions.push(position);

        let diff = position - positions[level];
        width = Math.max(width, diff + 1);

        dfs(node.left, level + 1, diff * 2);
        dfs(node.right, level + 1, diff * 2 + 1);
    }

    dfs(root, 0, 0)

    return width;
};

 

이진 트리의 최대 너비를 계산하는 함수

 

 

• positions: number[] = [0];
  • 각 레벨에서 가장 왼쪽 노드의 위치를 저장하기 위한 배열. 초기 값은 0
• width: number = 0;
  • 최대 너비를 저장하기 위한 변수. 초기 값은 0
• function dfs(node: TreeNode | null, level: number, position: number)
  • DFS (깊이 우선 탐색)을 이용해 트리를 순회하는 재귀 함수.
  • node는 현재 노드를 나타내며, null일 수 있다.
  • level은 현재 노드의 레벨(깊이)
  • position은 현재 노드의 위치를 나타냄
• if(!node) return;
  • 현재 노드가 null인 경우, 재귀 호출을 종료
• if(positions[level] === undefined) positions.push(position);
  • 현재 레벨의 가장 왼쪽 노드의 위치를 저장.만약 현재 레벨이 처음 등장하는 경우, 위치를 추가.
• let diff = position - positions[level];
  • 현재 노드의 위치와 해당 레벨의 가장 왼쪽 노드의 위치의 차이를 계산.
• width = Math.max(width, diff + 1);
  • 현재 레벨에서의 너비를 계산하고, 최대 너비를 업데이트
• dfs(node.left, level + 1, diff * 2);
  • 왼쪽 자식 노드를 다음 레벨로 재귀 호출. 왼쪽 자식 노드의 위치는 diff * 2로 계산.
• dfs(node.right, level + 1, diff * 2 + 1);
  • 오른쪽 자식 노드를 다음 레벨로 재귀 호출. 오른쪽 자식 노드의 위치는 diff * 2 + 1로 계산.
• dfs(root, 0, 0)
  • 트리의 루트 노드에서 탐색을 시작. 초기 레벨은 0이고, 초기 위치는 0
• return width;
  • 최대 너비를 반환

---

diff의 의미

diff는 현재 노드의 위치(position)와 해당 레벨에서 가장 왼쪽 노드의 위치(positions[level])의 차이

 

let diff = position - positions[level];

이 diff는 현재 노드가 해당 레벨의 가장 왼쪽 노드로부터 얼마나 떨어져 있는지를 나타냄

 

너비의 계산

이진 트리의 특정 레벨에서의 너비는 그 레벨에서 가장 왼쪽 노드부터 가장 오른쪽 노드까지의 거리에 해당.

예를 들어, 레벨 2의 노드 위치가 0, 1, 3이라면, 이 레벨의 너비는 가장 왼쪽 노드의 위치(0)와 가장 오른쪽 노드의 위치(3) 간의 거리,

즉 3 - 0 + 1 = 4

 

diff + 1의 의미

diff는 현재 노드의 위치와 가장 왼쪽 노드의 위치 차이이므로, diff + 1은 해당 레벨에서 현재 노드를 포함한 너비를 의미

 

 

        1
       / \
      3   2
     / \   \
    5   3   9

 

트리 노드의 위치를 다음과 같이 정의:

• 루트 노드의 위치는 0.
• 각 노드의 왼쪽 자식의 위치는 부모의 위치 * 2.
• 각 노드의 오른쪽 자식의 위치는 부모의 위치 * 2 + 1.

이제 트리의 레벨별 노드 위치를 살펴보겠습니다:

• 레벨 0: [1] -> 위치: [0]
• 레벨 1: [3, 2] -> 위치: [0, 1]
• 레벨 2: [5, 3, 9] -> 위치: [0, 1, 3]

레벨 2에서 노드 5의 위치는 0, 노드 3의 위치는 1, 노드 9의 위치는 3

 

width 업데이트 과정

레벨 2에서:

• positions[level]은 0 (가장 왼쪽 노드의 위치)
• 노드 5의 diff = 0 - 0 = 0 -> 너비는 0 + 1 = 1
• 노드 3의 diff = 1 - 0 = 1 -> 너비는 1 + 1 = 2
• 노드 9의 diff = 3 - 0 = 3 -> 너비는 3 + 1 = 4

여기서 최종적으로 width는 4

---

 

예시

        1
       / \
      3   2
     / \   \
    5   3   9

 

트리 노드 위치

트리 노드의 위치를 다음과 같이 정의:

• 루트 노드의 위치는 0입니다.
• 각 노드의 왼쪽 자식의 위치는 부모의 위치 * 2.
• 각 노드의 오른쪽 자식의 위치는 부모의 위치 * 2 + 1.

코드 실행 과정

1. 초기 상태:
   • positions = [0] (루트 노드의 위치는 0으로 초기화)
   • width = 0
2. 루트 노드(1)에서 시작:
   • dfs(1, 0, 0)
   • 레벨 0에서 노드 1의 위치는 0
   • positions = [0] (이미 초기화됨)
   • diff = 0 - 0 = 0
   • width = Math.max(0, 0 + 1) = 1
3. 왼쪽 자식 노드(3)로 이동:
   • dfs(3, 1, 0 * 2) = dfs(3, 1, 0)
   • 레벨 1에서 노드 3의 위치는 0
   • positions = [0, 0] (레벨 1의 첫 위치 0 추가)
   • diff = 0 - 0 = 0
   • width = Math.max(1, 0 + 1) = 1
4. 왼쪽 자식 노드(5)로 이동:
   • dfs(5, 2, 0 * 2) = dfs(5, 2, 0)
   • 레벨 2에서 노드 5의 위치는 0
   • positions = [0, 0, 0] (레벨 2의 첫 위치 0 추가)
   • diff = 0 - 0 = 0
   • width = Math.max(1, 0 + 1) = 1
   • dfs(null, 3, 0 * 2) (왼쪽 자식 노드가 null이므로 반환)
   • dfs(null, 3, 0 * 2 + 1) (오른쪽 자식 노드가 null이므로 반환)
5. 오른쪽 자식 노드(3)로 이동:
   • dfs(3, 2, 0 * 2 + 1) = dfs(3, 2, 1)
   • 레벨 2에서 노드 3의 위치는 1
   • diff = 1 - 0 = 1
   • width = Math.max(1, 1 + 1) = 2
   • dfs(null, 3, 1 * 2) (왼쪽 자식 노드가 null이므로 반환)
   • dfs(null, 3, 1 * 2 + 1) (오른쪽 자식 노드가 null이므로 반환)
6. 오른쪽 자식 노드(2)로 이동:
   • dfs(2, 1, 0 * 2 + 1) = dfs(2, 1, 1)
   • 레벨 1에서 노드 2의 위치는 1
   • diff = 1 - 0 = 1
   • width = Math.max(2, 1 + 1) = 2
7. 오른쪽 자식 노드(9)로 이동:
   • dfs(9, 2, 1 * 2 + 1) = dfs(9, 2, 3)
   • 레벨 2에서 노드 9의 위치는 3
   • diff = 3 - 0 = 3
   • width = Math.max(2, 3 + 1) = 4
   • dfs(null, 3, 3 * 2) (왼쪽 자식 노드가 null이므로 반환)
   • dfs(null, 3, 3 * 2 + 1) (오른쪽 자식 노드가 null이므로 반환)

결론

이 과정을 통해 너비가 가장 넓은 레벨은 레벨 2이며, 최대 너비는 4.

이는 노드 5, 3, 9가 포함된 레벨에서 너비가 4임을 나타냄