Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).
The binary search tree is guaranteed to have unique values.
Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32
Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23
The number of nodes in the tree is at most 10000.
The final answer is guaranteed to be less than 2^31.
이진탐색트리의 루트 노드가 주어질 때, L과 R을 포함하여 그 사이에 있는 모든 값들의 합을 반환한다.
이진탐색트리는 모두 유니크한 값을 가진다.
// 범위에 해당하지 않으면 다음 처리로 넘긴다.
// 범위에 해당하면 합산하고, 좌우값을 다음 처리로 넘긴다.
// 재귀적으로 처리한다.
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rangeSumBST(root *TreeNode, L int, R int) int {
sum := 0
if root == nil {
return 0
}
if root.Val < L {
return rangeSumBST(root.Right, L, R)
}
if root.Val > R {
return rangeSumBST(root.Left, L, R)
}
sum += root.Val
return sum + rangeSumBST(root.Left, L, R) + rangeSumBST(root.Right, L, R)
}
func rangeSumBST(root *TreeNode, L int, R int) int {
if root == nil {
return 0
}
sum := 0
switch {
case root.Val < L:
sum = rangeSumBST(root.Right, L, R)
case R < root.Val:
sum = rangeSumBST(root.Left, L, R)
default:
sum += root.Val
sum += rangeSumBST(root.Left, L, R)
sum += rangeSumBST(root.Right, L, R)
}
return sum
}
func rangeSumBST(root *TreeNode, L int, R int) int {
stack := []*TreeNode{}
sum := 0
for root != nil || len(stack) > 0 {
for root != nil {
stack = append(stack, root)
if root.Val > L {
root = root.Left
} else {
root = nil
}
}
root = stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
if root.Val >= L && root.Val <= R {
sum += root.Val
}
if root.Val < R {
root = root.Right
} else {
root = nil
}
}
return sum
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rangeSumBST(root *TreeNode, L int, R int) int {
if root == nil {
return 0
}
return helper(root, L, R)
}
func helper(node *TreeNode, L int, R int) int {
summary := 0
if node.Val >= L && node.Val <= R {
summary += node.Val
}
// 값이 합산조건에 들어가면 왼쪽 값을 다음 처리에 넘김
if node.Left != nil && node.Val > L {
summary += helper(node.Left, L, R)
}
// 값이 합산조건에 들어가면 오른쪽 값을 다음 처리에 넘김
if node.Right != nil && node.Val < R {
summary += helper(node.Right, L, R)
}
return summary
}
처음엔 이진탐색트리의 개념부터 공부했다.
그리고 익숙하지 않은 언어로 구현하려니 막막해서, 가장 익숙한 PHP로 접근한 것을 참고하였다.