[Leetcode] 662. Maximum Width of Binary Tree

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

---

이진 트리의 루트가 주어지면 트리의 최대 너비를 구하라.

최대 너비는 모든 레벨 중 최대 너비이며, 한 레벨의 너비는 가장 왼쪽 노드와 가장 오른쪽 노드의 길이이다. 만약 노드들 사이에 null 노드가 존재한다면 null 노드도 길이에 포함시킨다.

---

이진트리의 인덱스

이진트리의 인덱스를 구해보면 위와 같다.

특정 노드의 왼쪽 자식 노드의 인덱스는 2 x 인덱스. 오른쪽 자식 노드의 인덱스는 2 x 인덱스 + 1 이다.

이를 이용하여 루트 노드부터 자식 노드들을 탐색해가며 각 레벨에서 가장 왼쪽에 존재하는 노드와 가장 오른쪽에 존재하는 노드의 인덱스 차이가 너비가 된다. 구한 너비들 중 최대값이 정답이 된다.

 

시간복잡도는 노드의개수가 N이면 O(N).

---

소스코드

C++ : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/662.%20Maximum%20Width%20of%20Binary%20Tree.cpp

python : https://github.com/fpdjsns/Algorithm-python/blob/main/leetcode/medium/662.%20Maximum%20Width%20of%20Binary%20Tree.py