Range Sum of BST

Range Sum of BST

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

算法分析

本题主要考察的是二叉查找树的广度优先遍历，可以借助一个队列（slice），完成对二叉树元素的遍历。又由于这是一个二叉查找树。所以可以进行粗略的筛选，例如：如果当前节点的值小于给定范围的最小值，那么当前节点的左子树部分不需要在进入队列进行判断（也一定小于给定范围的最小值），只需要把当前节点的有子树入队列（起码他有一定的可能性大于给定范围的最小值）。通过这种遍历的方法，最后获取和值。

代码示例如下所示：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rangeSumBST(root *TreeNode, L int, R int) int {
    
    rsInt := 0
    
    // 借助一个队列对二叉查找树做广度优先遍历
    tmpList := []*TreeNode{root}
    
    for {
        if len(tmpList) == 0 {
            break
        }
        
        tmpList_ := []*TreeNode{}
        for _, v := range tmpList {
            if v.Val >= L && v.Val <= R {
                rsInt += v.Val
                if v.Left != nil {
                    tmpList_ = append(tmpList_, v.Left)
                }
                if v.Right != nil {
                    tmpList_ = append(tmpList_, v.Right)
                }
            } else if v.Val > R {
                if v.Left != nil {
                    tmpList_ = append(tmpList_, v.Left)
                }
            } else {
                if v.Right != nil {
                    tmpList_ = append(tmpList_, v.Right)
                }
            }
        }
        
        tmpList = tmpList_
    }
    return rsInt
}