JavaScript로 이진탐색트리 범위 안의 값 모두 더하기
문제분석
Binary Search Tree 의 루트와함께 Range(L, R) 이 함수의 파라미터로 들어올 때, L과 R사이에 포함되어 있는 모든 값을 더해서 리턴하는 함수를 구현하라
돌파구
먼저, 이진탐색트리의 성질을 이용하기 전에, 이진트리의 DFS를 생각 해 본다. 모든 값을 방문해서 현재 노드의 값이 L과 R사이 일 때, 그 값을 더해주기만 하면 된다.
하지만, 함수의 인자로 들어오는 트리가 이진탐색트리 일 때에는, 모든 노드를 다 방문 할 필요가 없다. 범위를 벗어난 노드에 대해서는 탐색 해 줄 필요가 없는 것이다. 이렇게 하면, 탐색에 소요되는 시간과, 재귀호출을 줄여서 메모리 사용을 줄일 수 있다.
구현
결론적으로, DFS를 재귀로 구현한 것에서 발전시키면 되는데, 이 때 필요없는 탐색을 줄이기 위해서 조건문이 필요하다.
if(L > node.val): 현재 노드의 value 가 L 보다 작을 때에는 이 노드의 왼쪽은 항상 현재 노드의 value 보다 작은 값만 있으니까, 더이상 검사 해 줄 필요가 없다. 따라서dfs(node.right)오른쪽만 재귀호출 하면된다.if(node.val > R): 이번에도 마찬가지로 현재 노드의 value 가 R 보다 클 때에는 이노드의 오른쪽은 항상 큰 값만 있으니까,dfs(node.left)왼쪽에 대해서만 재귀호출을 한다.if(L <= node.val && node.val <=R): 범위 안에 들어올 때에는, 현재값을 sum 에 더해주고, 왼쪽과 오른쪽에 대해서 더 검사 해 준다.dfs(node.left), dfs(node.right)
