타입챌린지 : 3376-InorderTraversal (medium)

이 글은 제가 타입챌린지를 하면서 해석한 내용을 적는 글입니다. 틀린 내용이 있으면 댓글 달아주시면 감사하겠습니다.

 

https://github.com/type-challenges/type-challenges/blob/main/questions/03376-medium-inordertraversal/README.md

 

 

 

일단 내가 푼 답을 봐보자.

interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}
type InorderTraversal<T extends TreeNode | null> = T extends TreeNode
  ? T['left'] extends TreeNode
    ? [...InorderTraversal<T['left']>, T['val']]
    : T['right'] extends TreeNode
      ? [T['val'], ...InorderTraversal<T['right']>]
      : [T['val']]
  : []

역시 재귀로 풀었다. 재귀로 안풀고 InorderTraversal에 디폴트로 제네릭 U extends any[] = []을 두어서 배열에 값을 저장하게끔 하는 방법도 있다.

T extends TreeNode ? T['left'] extends TreeNode : T가 TreeNode라면 left를 먼저 탐색하는데, 이 T['left']도 TreeNode인지 확인한다.

? [...InorderTraversal<T['left']>, T['val']] : T['left']가 TreeNode라면 left를 다시 탐색하는데, 현재 노드의 값을 배열의 뒤쪽에 담는다.

: T['right'] extends TreeNode ? [T['val'], ...InorderTraversal<T['right']>] : T가 null이라면 right를 탐색하는데, T['right']가 TreeNode라면 현재 노드의 값을 배열의 앞쪽에 담고 오른쪽 노드를 탐색한다.

: [T['val']] : [] : right도 null이면 현재 노드의 값을 배열에 담아서 리턴한다. 그것도 아니라면 빈 배열을 리턴한다.

 

 

그리고 이제 다른 사람의 답을 봐보자.

type InorderTraversal<T extends TreeNode | null, NT extends TreeNode = NonNullable<T>> = T extends null
  ? []
  : [...InorderTraversal<NT['left']>, NT['val'], ...InorderTraversal<NT['right']>]

이것도 재귀다. 근데 내꺼보다 훨씬 짧다...

T가 null이면 빈 배열을 리턴하고 T가 TreeNode라면, left와 right를 모두 전개연산자로 풀어서 배열을 리턴해버리는.. 진짜 천재적인 답인 것 같다... 나는 왜 이런 생각을 못했을까.