22 -- 二叉搜索树的范围和

1. 题目

GitHub刷题链接

• 题目的意思就是说：
  遍历所有的节点，只要节点的值在范围内，就求和，如果不在范围内，就不算进来

2. 思路

• 理解了题目的意思，就容易求了。
• 通过DFS遍历求和。

    var sum = 0

    func rangeSumBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
        dfs(root: root, low: low, high: high)
        return sum
    }

    func dfs(root: TreeNode?, low: Int, high: Int) {
        if root == nil {
            return
        }
        if root!.val >= low && root!.val <= high {
            sum += root!.val
        }
        dfs(root: root?.left, low: low, high: high)
        dfs(root: root?.right, low: low, high: high)
    }

• 思路二
  BFS
  但是效率慢很多
  代码：

    var sum = 0
    var queue: [TreeNode] = [TreeNode]()
    
    func rangeSumBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> Int {
        if root == nil {
            return sum
        }
        
        bfs(root: root, low: low, high: high)
        
        return sum
    }
      func bfs(root: TreeNode?, low: Int, high: Int) {
        if root != nil {
            queue.append(root!)
        }
        
        while !queue.isEmpty {
            let node = queue.removeFirst()
            let value = node.val
            
            if value >= low && value <= high {
                sum += value
            }
            
            if node.left != nil {
                queue.append(node.left!)
            }
            
            if node.right != nil {
                queue.append(node.right!)
            }
        }
    }
  

3. 提交

BFS: 2504ms

DFS: 420 ms