이진트리 넓이 구하기 문제(이진탐색, 인덱스)
이진트리 넓이 구하기 문제(이진탐색, 인덱스) — #이진트리 #이진트리문제 #이진트리넓이 #이진탐색 #이진트리인덱스 #개발자의도구들 사용된 언어: 코틀린,...
#이진트리 #이진트리문제 #이진트리넓이 #이진탐색 #이진트리인덱스 #개발자의도구들
- 사용된 언어: 코틀린, 혹은 파이썬
- 순서: 로직, 코드 구현, 코드 분석
트리의 넓이 구하기
LeetCode(medium 662. Maximum Width of Binary Tree)
/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
class Solution {
fun widthOfBinaryTree(root: TreeNode?): Int {
}
}
// 1~3000개의 노드
생각하기
1. 넓이를 구하려면 leaf를 주목해야한다.(뭔가 패턴이 보인다)
- level 1에서 가능한 최대 넓이는 2 (level 0 = root)
- level 2에서 가능한 최대 넓이는 4
- level 3에서 가능한 최대 넓이는 8
2. level이 높다고 해서 width가 크다는 것을 보장할 수 없다.
- level 2의 제일 좌측 < level 1의 우측
3. 여러가지 고민 끝에 한가지 패턴을 발견했다.
- level m의 다음 level이 n이라고 할 때 lead 노드는 [1, 2, ... 2^n] 이렇게 표현이 가능하다.
- 그럼 m에서 right로 이동한다면, 다음 노드(n)가 가질 수 있는 최소 인덱스는 2^(n-1) + 1이다.
- left의 경우에는 최대 인덱스가 2^n이 된다.
- 이점을 이용해서 각 노드는 레벨에서 자신이 몇 번째 인덱스인지 계산이 가능하다.
🏗️ 각 노드에서 할 일
받는 것 : 부모의 레벨 정보, 자신에게 까지 흘러온 경로
1. 레벨 정보를 확인하여, 자신의 레벨을 결정
2. 패스 경로를 확인하여, 자신의 width값 계산
ex) 자신이 lv 1에 존재하면, 최대 범위는 1 2 이다.
이때 path를 확인하였는데 left라면 자신은 1임을 알 수 있다.
넘겨 줄 것: 자기 자식에게 level 및 새로운 path
1차 시도
class Solution {
var maxWidth = -1
fun updateMw(root: TreeNode?, level: Int, path:MutableList<Int>) {
println("now position ${root?.`val`}")
if (root == null) return
val myLevel = level + 1
var s = 1
var e = 1 shl myLevel
for (p in path) {
if (p == 0) {
e = (s + e) / 2
} else if (p == 1) {
s = (s + e) / 2 + 1
}
println("in level $myLevel update s, e ($s, $e)")
}
// maxWidth update
maxWidth = maxOf(maxWidth, s, e)
val leftPath = path.toMutableList()
leftPath.add(0) // 얕은 복사 필요
val rightPath = path.toMutableList()
rightPath.add(1)
updateMw(root.left, myLevel, leftPath)
updateMw(root.right, myLevel, rightPath)
}
fun widthOfBinaryTree(root: TreeNode?): Int {
if (root == null) {
return 1
}
updateMw(root.left, 0, mutableListOf(0))
updateMw(root.right, 0, mutableListOf(1))
return maxWidth
}
}
// 1~3000개의 노드
현재 노드의 index값 중 가장 큰 놈을 계산하는 로직이다. 근데 틀렸다. 문제를 잘못 이해했다. 문제에서 정의된 넓이는 index가 가장 큰 node를 찾는 것이 아니라, 해당 level에서 가장 작은 index노드와 가장 큰 index 노드의 차이를 구해야한다.
위 코드를 조금만 손보면 뭔가 해결 될 것 같은 느낌이 들었다.
2차시도
로직을 수정하자.
각 레벨의 최소 인덱스와, 최대 인덱스를 저장해 둬야 한다. hashMap은 어떨까?
{key: value}
{level: Tuple(min, max)} 이렇게 저장해두면 최소, 최대값을 업데이트하기가 쉽다.
/**
* Example:
* var ti = TreeNode(5)
* var v = ti.val
* Definition for a binary tree node.
* class TreeNode(var val: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
data class MutablePair(var minIndex: Int, val maxIndex: Int)
class Solution {
// {level: (min, max)}
var indexMap: MutableMap<Int, MutablePair> = mutableMapOf()
fun updateMw(root: TreeNode?, level: Int, path:MutableList<Int>) {
// println("now position ${root?.val}")
if (root == null) return
val myLevel = level + 1
if (indexMap[myLevel] == null) {
indexMap += myLevel to MutablePair(Int.MAX_VALUE, -1)
}
var s = 1
var e = 1 shl myLevel
for (p in path) {
if (p == 0) {
e = (s + e) / 2
} else if (p == 1) {
s = (s + e) / 2 + 1
}
// println("in level $myLevel update s, e ($s, $e)")
}
// check now index is min or max
// println("compare min, ${indexMap[myLevel]!!.minIndex}, ${e}")
val minIndex = minOf(indexMap[myLevel]!!.minIndex, e)
// println("compate max, ${indexMap[myLevel]!!.maxIndex}, ${e}")
val maxIndex = maxOf(indexMap[myLevel]!!.maxIndex, e)
// update min, max
indexMap[myLevel] = MutablePair(minIndex, maxIndex)
// println("map updated, ${indexMap[myLevel]}")
// add path left, right
val leftPath = path.toMutableList() // shallow copy
leftPath.add(0)
val rightPath = path.toMutableList()
rightPath.add(1)
updateMw(root.left, myLevel, leftPath)
updateMw(root.right, myLevel, rightPath)
}
fun widthOfBinaryTree(root: TreeNode?): Int {
if (root == null) {
return 1
}
indexMap.put(0, MutablePair(1, 1)) // init map
updateMw(root.left, 0, mutableListOf(0))
updateMw(root.right, 0, mutableListOf(1))
//print("all updated $indexMap")
var maxWidth = -1
var choicedLevel = 0
for ((level, idxPair) in indexMap) {
maxWidth = maxOf(idxPair.maxIndex - idxPair.minIndex + 1, maxWidth)
choicedLevel = level
}
println("choiced : $choicedLevel ,$(indexMap[choicedLevel]!!)")
return maxWidth
}
}
이제 모든 Level에서 최대/ 최소가 업데이트 되고 최종적으로 모든 Pair를 순회하여 넓이 값을 계산하여 가장 큰 넓이를 반환한다.
🤬 나타난 문제들
- 예시입력에서 깊이가 30이 상이 넘어가는 케이스가 주어진다.
- 이러면 Integer에서 shif연산과 + 연산등에 의해서 범위 초과로 의도치 않는 값이 발생하여
결과가 10억 이렇게 나온다.
범위 오류로 인해서 Long으로 변경햇는데, 이번에는 깊이가 500이 넘어가더니 계속해서 고정적으로 3의 값이 나온다. 이후 BigInteger로도 시도했으나 성과는 없었다 .... (내 시간을 돌려줘...)
문제를 개선하기 위해서는 근본적으로 코드를 전부 수정해야 겠다는 결론을 내렸다. 아니 애초에 내 코드가 틀린게 분명하다..
인덱스에 대한 새로운 접근
공부를 하고나니 이진트리를 모르는구나라는 생각이 들었다.. 해당 노드의 인덱스는 부모 노드 자신의 정보로 부터 구할 수 있었던 것이다...
왼쪽 자식의 인덱스 = 자신의 인덱스 * 2L (최대한 Long type으로 주자)
오른쪽 자식의 인덱스 = 자신의 인덱스 * 2L + 1
1 (idx = 0)
/ \
2(0) 3(1)
/ \ / \
5(0) 6(1) 3(2) 4(3)
/ \ / \ / \ / \
4(0) 5(1) 3(2) 4(3) 3(4) 5(5) 2(6) 4(7)
.......
이럴수가... 이원리만 적용하면 자식 인덱스를 매우 쉽게 구할 수 있다...
정답코드
사실 이 원리를 알고나서 더 이상 정답 코드를 작성하는 것이 의미가 없다는 생각이 들었다. 기본적인 로직 자체는 크게 다를바 없다. 어떤 자료형이든 알고리즘을 쓰든 결국에는 index만 구하는 방법만 변경되었기 때문이다.
지금 다시 코드를 리뷰하면서 느낀건,, 아무래도 s + e 과정에서 오류가 나는게 있었지 않을까? 라는 생각이다... 너무 숫자가 커지면 다루기가힘들다. Long을 사용햇는데도 안되는 거면, 접근 방법부터 의심해보자.
🆕 updated
새로운 인덱스 계산 방법을 이용하여 정답코드를 정리하려 했으나, 코드 수를 줄이고자 BFS로 시도했다. 다음은 BFS 코드의 정답과, 공부를 하며 얻은 insight들이다.
class Solution {
fun widthOfBinaryTree(root: TreeNode?): Int {
if (root == null) return 0
var maxWidth = 0
var q: MutableList<Pair<TreeNode, Int>> = mutableListOf()
q.add(root to 0) // isRight?
while (q.isNotEmpty()) {
var l = -1 // for level initial position check
repeat(q.size) {
val (n, idx) = q.removeAt(0) // s right?
n.left?.let {
q.add(it to idx * 2)
}
n.right?.let {
q.add(it to idx * 2 + 1)
}
if (l == -1) l = idx
maxWidth = maxOf(idx - l + 1, maxWidth)
}
}
return maxWidth
}
}
// idx를 구하기 위해 부모의 idx를 받아온다.
// 각 노드는 부모의 idx를 참고하여 자신의 idx를 갱신 후 자식에게 전달한다.
// 자신의 레벨은 어떻게 정리할 것인지?
// 각 Level의 정보가 담긴 구조로 갱신 ?
// 출처 : dzmtr
BFS
BFS 사용시 가장 고민이 되었던 부분은 Level을 어떻게 결정해야 하는지에 대해서였다. 물론 기존의 해쉬맵을 사용해서 각 레벨의 min과 max를 업데이트 할 수는 있다. 근데 이렇게 하기에는 뭔가 아쉬웠다.
도저히 생각이 나지 않아서 solution을 참고하였다. 방법은 매우 간단했는데, BFS를 각 레벨별로 묶어서 돌리고, 가장 첫번째 node의 idx만 따로 기입하는 것이다.
기존의 BFS는 선형적으로 탐색을 했었다. 레벨 정보를 따로 저장이 필요했다. 하지마 오른쪽과 같이 탐색을 하면 level정보를 탐색하는 내부에서 관리가 가능하다.
이를 가능하게 하려면, while 내부에 for문을 두어 각 레벨별로 q의 모든 내용을 소진 시키고 다음 레벨로 넘어가는 것이다.
while (q.isNotEmpty()) {
var l = -1 // for level initial position check
repeat(q.size) { // level contianer
val (n, idx) = q.removeAt(0) // s right?
n.left?.let {
q.add(it to idx * 2)
}
n.right?.let {
q.add(it to idx * 2 + 1)
}
if (l == -1) l = idx
maxWidth = maxOf(idx - l + 1, maxWidth)
}
}
위 코드에서는 repeat()으로 level을 묶어서 처리하였다. 이러고 보니 Long을 사용하지 않아도 된다는 사실을 깨닫게 되었다..
필요했던 지식들
1. 코틀린 map 사용하기
선언 : myMap :MutableMap<String, Int> = mutableMapOf()
저장/갱신 : myMap["A"] = 1 or myMap += "A" or myMap.put("A", 1)
to 1 (개인적으로 마음에 드는 방식)
삭제 : myMap.remove(AAA) or myMAp -= "A" / myMap.clear() 모두 삭제
key확인: myMap["A'] 가 없다면 null을 반환함
조회 : MyMap["A"] or myMap.getIrNull("A")
반복문에서 사용하기
for ((key, value) in myMap) {
}
key만
for (key in myMap.keys) {}
value만
for (value in myMap.values) {}
+ 최대, 최소
myMap.minByOrNull {it. value} 최소값을 가지는 key값
myMap.values.minOrNull // 최솟값 없으면 null로
2. MutableList를 Queue처럼 사용하기
-- 맨 앞의 요소 제거: removeAt(0)
-- 없어질 때까지 반복하기: q.isNotEmpty()
3. 반복문 편하게 사용하기
-- repeat(n) n = 반복할 횟수
파이썬이랑 코드가 거의 비슷해서 너무 편리하다.