본문 바로가기
알고리즘 문제/Leetcode

[leetcode][938] Range Sum of BST

by 햄과함께 2018. 11. 12.
반응형

문제 : https://leetcode.com/problems/range-sum-of-bst/




BST는 왼쪽 자식 서브트리는 현재 노드보다 값이 작고, 오른쪽 자식 서브트리는 현재 노드보다 값이 크다.

따라서 현재 노드의 val가 L보다 크다면 왼쪽 서브트리에도 정답이 될 수 있는 노드가 있을 수도 있다. -> 왼쪽 서브트리 탐색.

현재 노드의 val가 R보다 작다면 오른쪽 서브트리에도 정답이 될 수 있는 노드가 있을 수 있다. -> 오른쪽 서브트리 탐색.

루트 노드부터 위 조건에 맞는 서브트리를 탐색해 가면서 정답이 될 수 있는 수를 더해간다.


시간복잡도는 O(노드개수).




소스코드 : https://gist.github.com/fpdjsns/8818a1684ee7bb59abfb404ff6dd792e

반응형

태그

댓글0