JavaScript로 이진트리 대칭인지 확인하는 함수 구현하기
문제분석
이진트리의 root가 함수의 인자로 들어올 때, 트리가 root 노드(중간)을 기준으로 대칭인지 return 하기
돌파구
Iteratively(Breadth First Search)
너비우선탐색 알고리즘을 사용해서, 층마다 구분을 한다. 각 층 마다 node 의 값들을 포함하는 배열을 만들어서 대칭인지 비교하는 함수를 따로 구현했다. 이 때, 한번이라도 false 를 만나면 false 리턴하면 된다.
Recursively(Depth Frist Search)
마치 root를 기준으로 거울이 있다고 가정한다. 거울을 대칭으로 트리의 안쪽과 바깥쪽이 같아야 대칭이 되는 것이다. value 가 같으면 탐색을 이어나가고, 값이 같지 않으면 false를 리턴한다.
구현
Iteratively(Breadth First Search)
- check(depth): 넘겨받은 너비(층)이 대칭인지 확인하는 함수
- bfs(root): 너비우선탐색 알고리즘으로 매 너비(층) 마다 depth 배열을 생성해서, check 함수에 넘겨준다.
- Runtime: 104 ms, faster than 8.51% of JavaScript online submissions for Symmetric Tree.
- Memory Usage: 35.7 MB, less than 70.00% of JavaScript online submissions for Symmetric Tree.
- Runtime: 144 ms, faster than 5.90% of JavaScript online submissions for Symmetric Tree.
- Memory Usage: 35.4 MB, less than 100.00% of JavaScript online submissions for Symmetric Tree.
결과를 보아하니, 메모리 사용량은 적지만, 속도가 하위 10퍼센트에 속한다.
Recursively
dfs 알고리즘은 mirroring 알고리즘이다.
- ending 조건은, 둘 다 null 일 때, 최하단에 닿은 것 true return
- 둘 중 하나라도 null 이면, 비대칭 이므로 false return
- 값이 같지 않을 때 비대칭 false return
- 값이 같을 때, 아래층에 대해 탐색을 이어 나간다. 이 때 주의해야 할 점이 거울을 기준으로 안쪽과 바깥쪽이 같은지를 비교해야한다.
- Runtime: 100 ms, faster than 9.63% of JavaScript online submissions for Symmetric Tree.
- Memory Usage: 35.5 MB, less than 100.00% of JavaScript online submissions for Symmetric Tree.
속도가 나아지지 않는다. 어떻게 해야 시간복잡도를 줄일 수 있을까..?
