Leetcode 662. Maximum Width of Binary Tree (BFS level order)

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

Maximum Width of Binary Tree - LeetCode

 

---

다시 만난 Binary Tree 문제입니다.

이진트리의 레벨에서 최대 길이(시작 노드에서 끝노드까지의 개수)를 찾는 문제입니다.

 

처음에 level order traversal 임을 파악하고 BFS로 접근을 시도했는데요, 어떻게 길이의 정의를 코드화시킬 수 있을까 를 헤매다가 다른 답안 분석을 통해 힌트를 얻을 수 있었습니다.

 

이 코드는 다른 답안들을 보면서 작성한 코드입니다

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        dq = deque([(0,root)])
        currmax = 0
        while dq:
            level_idx = []
            for _ in range(len(dq)):
                id, node = dq.popleft()
                level_idx.append(id)
                if node.left:
                    dq.append((2*id+1,node.left))
                if node.right:
                    dq.append((2*id+2,node.right))
            currmax = max(currmax,level_idx[-1]-level_idx[0]+1)
        return level_idx

 

BFS를 실행하기 위해 deque를 호출하고 각 레벨의 인덱스를 담는 level_idx 그릇을 만들어줍니다.

그리고 자식노드의 수만큼 = level에 있는 노드만큼 순회하면서 인덱스값을 담아줍니다.

 

만약, level order을 반환해야 한다면 인덱스를 담는게 아니라 일반 append(node.left) 혹은 append(node.right) 이 됐겠지만

문제의 목적 자체가 '길이'를 구하는 것이기 때문에 별도로 순환값을 기록하지는 않았습니다.

 

제가 길을 잃었던 어떻게 하면 '길이'를 구할 수 있을까? 를 

2*id +1, 2*id+2로 해결했는데요

 

           0

    1            2

3    4       5    6

 

이렇게 binary tree가 있을 때 왼쪽에 있는 노드의 인덱스 값은 부모노드의 인덱스 *2 +1

오른쪽 노드의 인덱스 값은 부모노드의 인덱스*2 +2 의 값으로 해석될 수 있기 때문에 이런 접근이 가능한 것이죠!

 

그리고 마지막에 '최대길이'는 가령 레벨에 [3,4,5] 가 있다면 level_idx 자체가 정렬된 형태로 쌓이기 때문에

끝값-첫번째값+1이라는 형식으로 도출이 가능합니다.

 

---

코드 간소화 버전)

def widthOfBinaryTree(self, root):
    width = 0
    level = [(1, root)]
    while level:
        width = max(width, level[-1][0] - level[0][0] + 1)
        level = [kid
                 for number, node in level
                 for kid in enumerate((node.left, node.right), 2 * number)
                 if kid[1]]
    return width

(Source: Leetcode StefanPochmann)

 

평소에도 많이 참고를 했었던 StefanPochmann의 코드를 가져왔습니다.

여기서 제일 기발했던 부분은 enumerate(iterable, start)의 start 부분에 2*number을 위치시켜서 부모 노드의 인덱스 값을 받아서 자식 노드의 인덱스 값이 계산되도록 했습니다! 제일 첫번째 풀이와는 달리 인덱스의 시작을 1로 해서

왼쪽 노드는 부모노드 인덱스*2, 오른쪽 노드는 부모노드 인덱스*2 +1 이런 식으로 구성되도록 했습니다.

 

                1
          2               3
      4       5       6       7
    8   9   ...

 

enumerate의 시작이 2*부모노드인덱스이므로 , child  값이  left, right 2개이기 때문에

right 에는 시작값 +1 = 2*인덱스 +1이 자연스럽게 할당되도록 했습니다.

 

 

(이해를 위해 2개의 for문이 들어있는 List Comprehension의 구성을 정리했습니다.)

• for문 2개를 활용한 List Comprehension

[가장 바깥 for 문 + 내부 for 문]   =    [ x for y in a for x in y]

 

 

728x90

 

간소화 풀어쓴 버전)

def maxWidthTree(root):
	width = 0
	level = [(1,root)]
	while level:
		temp = list()
		width = max(width, level[-1][0] - level[0][0] + 1)
		for number, node in level:
			for child in enumerate((node.left, node.right), 2*number):
				if child[1]:
					temp.append(child)
		level = temp
	return width

 

확실히 풀어쓴 버전이 좀 더 이해가 잘되는거 같긴 합니다.

 

---

Binary Tree 를 풀다보면 늘 stack이나 queue에 [(1,root)]이런식으로 괄호안에 추가적인 값이 함께 연산되도록 해서 

답안을 유도하는 경우가 많은 것 같습니다. 특히 이번 경우처럼 인덱싱이 필요한 경우, 유용하게 활용이 가능한 것 같네요

 

앞으로 BFS, DFS 문제를 만나면 꼭 떠올리도록 해봐야겠습니다 :))