Range Sum of BST

参考：https://leetcode.com/problems/range-sum-of-bst/

問題の内容:

例:

例1:
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32

    10
  5    15
3   7     18

例2:
Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23

     10
   5    15
 3  7  13 18
1  6

ヒント:

The number of nodes in the tree is in the range [1, 2 * 104].
1 <= Node.val <= 105
1 <= low <= high <= 105
All Node.val are unique.

DFSを使って、範囲内のvalueを全部プラスするなら、解決できます。

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun rangeSumBST(root: TreeNode?, low: Int, high: Int): Int {
        if(root == null){
            return 0
        }
        if(root.`val` < low){
            return rangeSumBST(root?.right,low,high)
        }
        if(root.`val` > high  ){
            return rangeSumBST(root?.left,low,high)
        }
        return  root.`val` + rangeSumBST(root?.right,low,high) +  rangeSumBST(root?.left,low,high)
    }
}