当前位置：网站首页>22 -- range and of binary search tree

22 -- range and of binary search tree

2022-07-24 02:30:00 【JH_ Cao】

1. subject

GitHub Brush topic link
Insert picture description here

The title means ：
Traverse all nodes , As long as the value of the node is within the range , Just sum , If it's not in range , Don't count in

2. Ideas

Understand the meaning of the topic , It's easy to ask .
adopt DFS Ergodic summation .

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

Train of thought two
BFS
But the efficiency is much slower
Code ：

  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!)
          }
      }
  }