JavaScript로 다중 자식 트리의 최대 깊이 값 구하기
문제분석
다중 자식 트리가 함수의 인자로 들어올 때, 가장 깊은 깊이를 리턴하기
돌파구
이진탐색트리의 깊이를 구할 때 사용한 DFS 알고리즘을, 다중 자식 트리에도 적용 해보자. 이진탐색트리의 노드가 this.left, this.right 로 주소를 가리키는 것에 반해, 다중자식트리는 this.children = [child reference, child reference ...] 로 주소를 배열에 저장하고 있는 형태다.
이진탐색트리에서 node.left, node.right 에 대해 dfs 함수를 재귀로 호출 하듯이, 각각의 자식에 대해서 dfs 함수를 호출하면 된다.
이 때, 자식을 가리키는 reference 가 각각 배열에 들어있으므로, reduce 함수로 각각의 child 에 대해서 매 번 dfs를 호출해서 깊이를 알아내고, max 를 계속해서 갱신하는 형태로 코드를 구현했다.
구현
- 재귀 호출이 끝나는 조건 : 들어온 노드가 null 이라면 길이 0을 리턴한다.
들어온 node 의 children 에는 배열이 들어있으므로 reduce 함수를 사용해서 모든 자식노드에 대해서 iterable 하게 깊이를 구하고, 가장 깊은 길이까지 갱신 해 보자.
const depth = dfs(child);자식 노드의 깊이를 구한다.return depth > max ? depth : max;로 max 값을 갱신한다.
- 리턴 : 최대 깊이를 return 한다.
