LeetCode日本語修行14日目- [938-指定範囲内二分探索木のSUM]
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)
}
}
Author And Source
この問題について(LeetCode日本語修行14日目- [938-指定範囲内二分探索木のSUM]), 我々は、より多くの情報をここで見つけました https://qiita.com/Aethey/items/80fef5b9bc7c3c2af23f著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .