JavaScript로 두개의 이진트리 병합하기
문제분석
두개의 이진트리가 함수의 인자로 들어올 때, 두 이진트리를 병합하기. 겹치는 부분은 value 가 증가되고, 둘 다 없을 때에는 비어있는 노드가 됨. 하나라도 있을 때에는 그 노드가 새로운 트리의 자리를 차지한다.
돌파구
이번에도 재귀! 보통 이진트리의 문제를 해결할 때에는 재귀로 하면 쉽게 풀린다. 역시나 자식노드에게 일을 위임하는 것. 부모노드가 ‘얘들아, 너희가 합쳐서 오면 받아줄게. 그러니까 합쳐서와~’ 라고 한다.
우리는 이 재귀 함수의 끝나는 조건과 리턴만 잘 명시 해 주면, 재귀를 타고 내려가서 밑에서 부터 알아서 트리가 합체되어서 루트까지 올라온다.
결국, 계속해서 DFS(Depth Frist Search) 알고리즘의 연장선상에 있는 것이다.
구현
- 재귀가 끝나는 조건 : Input 으로 들어온 node 두개 중 하나라도 null 이라면, 그 밑에 딸려있는 자식이 더 없다는 이야기다. 따라서
return node1 || node2를 리턴한다. const node = new TreeNode(node.val + node2.val): 같은 위치에 둘 다 노드가 있을 때에는 value 가 합쳐진 새로운 노드를 생성한다.- 왼쪽, 오른쪽 자식에게 일을 위임한다 : 왼쪽, 오른쪽 노드에 대해 재귀함수 호출
- 리턴 : 새로 만들어진 노드를 리턴한다. 그래야지 새롭게 만들어진 트리가 연결이 됨.
