[알고리즘] Leetcode_938_Range_Sum_of_BST

Problem

Solve

• BST 의 자신의 왼쪽 트리는 자기 값보다 작고, 자신의 오른쪽 트리는 자기 값보다 큰 특징을 이용한다.
• 재귀(DFS)를 이용해서 root.val 와 low, high 를 비교해간다.
  • 예외는 root.val 가 low와 high 사이에 오도록 내려간다.
    • root.val 가 low 보다 작을 경우에는 root.val 보다 값이 큰 root.right 로 내려간다.
    • root.val 가 high 보다 큰 경우에는 root.val 보다 값이 작은 root.left 로 내려간다.
  • 재귀의 base

    • root 가 null 일 때는 0을 리턴

    • root.val 가 low 나 high 와 동일할 때 = 예외가 아닌 경우 ⭐️
      - 예외가 없을 때는 root의 left 와 right 로 내려간다.

      
      

말이나 트리의 구조를 그림으로 보면서 문제를 해결을 하려고 하면 이해는 간다.
코드로 항상 작성하려하다 보면 재귀에서는 예외의 상황은 오히려 쉽다.
어려운 부분은 항상 base 부분과 예외가 아닌 상황이다.

원초적으로 함수의 반환되어야 하는 값은 합계이다!
1. base 부분은 대부분 root 가 null 일 경우이기 때문에 0을 리턴한다.
2. 이제 예외 상황이 아닌 경우에는 root.val 이 low와 high 사이 범주 내에 속한다는 의미이므로 자신의 값과 왼쪽 서브 트리와 오른쪽 서브 트리의 합계를 더해주면 된다. 이때도 재귀를 이용한다.
3. 예외 상황인 경우에는 자신의 값을 더해주지 않는다!!! 그냥 트리를 내려가기만 하면 되기 때문이다.

public int rangeSumBST(TreeNode root, int low, int high) {
        // root 가 null 인 경우에는 0을 리턴한다.
        if(root == null) return 0;

		// low 보다 작을 경우에는 low 보다 크거나 같은 값을 찾아주기 위해 
        // BST 의 특징을 이용해 오른쪽 서브트리로 이동한다.
        if(root.val < low) return rangeSumBST(root.right, low, high);

		// high 보다 클 경우에는 high 보다 작거나 같은 값을 찾아주기 위해 
        // BST 의 특징을 이용해 왼쪽 서브트리로 이동한다.
        if(root.val > high) return rangeSumBST(root.left, low, high);

       	// 위의 예외 상황이 아닌 경우에는
        // low <= root.val <= high 인 경우이기 때문에
        // 자신의 값을 더해주면서 왼쪽 서브트리와 오른쪽 서브트리에서의 재귀를 시작한다.
        return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
    }