[golang] LeetCode #938. Range Sum of BST

1. 문제

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.

Example 1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

Note:

The number of nodes in the tree is at most 10000.
The final answer is guaranteed to be less than 2^31.

해설

이진탐색트리의 루트 노드가 주어질 때, L과 R을 포함하여 그 사이에 있는 모든 값들의 합을 반환한다.

이진탐색트리는 모두 유니크한 값을 가진다.

2. 접근

// 범위에 해당하지 않으면 다음 처리로 넘긴다. 
// 범위에 해당하면 합산하고, 좌우값을 다음 처리로 넘긴다.
// 재귀적으로 처리한다. 

3. 내가 작성한 답

/**
 * 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)
}

4. 다른 유저의 답안

1. case구문을 활용

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
}

2. 배열을 이용. 다음에 다시 읽어보자.

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
}

3. 범위에 해당하지 않으면, 재귀적으로 처리함

/**
 * 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
}

5. 추가로 공부한 내용

처음엔 이진탐색트리의 개념부터 공부했다.
그리고 익숙하지 않은 언어로 구현하려니 막막해서, 가장 익숙한 PHP로 접근한 것을 참고하였다.

6. 참고사이트

1. ratsgo's blog - 이진탐색트리(Binary Search Tree)
2. GOLANG TUTORIAL - BINARY SEARCH TREE (BST) - PART 1 (TREE/NODE STRUCTS WITH INSERT AND PRINT FUNCTIONS)
   
3. Go Data Structures: Binary Search Tree
4. [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)