BST範囲検索、distribute coins

淡々と問題を解く

## 前回まで
配列 https://qiita.com/tsnb/items/983c32d83331de1e0bea
連結リスト https://qiita.com/tsnb/items/3028ee788ff77ebaaa5e
スタック https://qiita.com/tsnb/items/e6901249629ef090ee8f
キュー https://qiita.com/tsnb/items/588afe675ad830ff1fc6
二分木 https://qiita.com/tsnb/items/8aa4e1ebb24d87919c40
二分探索木 https://qiita.com/tsnb/items/8553f8c2effb4d704d9a
ヒープ https://qiita.com/tsnb/items/0fb42e62118d647b20d6
ソート https://qiita.com/tsnb/items/22ef2b129c0e598235c0

## BSTの範囲検索

[10,5,15,3,7,null,18]のような値をもつNodeに対して、L=7、R=15の間の範囲のリストを求める

全探索する時に、listに条件にマッチする値をブッ込んだだけ・・

```ruby
class Node
  attr_accessor :val, :left, :right

  def initialize(val)
    @val = val
    @left = nil
    @right = nil
  end

  def add_left(val)
    self.left = Node.new(val)
  end

  def add_right(val)
    self.right = Node.new(val)
  end
end

class Bst
  def initialize(val)
    @head = Node.new(val)
    @list = []
  end

  def mktree
    @head.add_left(5)
    @head.left.add_left(3)
    @head.left.add_right(7)
    @head.add_right(15)
    @head.right.add_right(18)
  end

  def traverse(node)
    @list << node.val      if @l <= node.val and node.val <= @r
    traverse(node.left)    if !!node.left
    traverse(node.right)   if !!node.right
  end

  def range_sum_bst(l, r)
    @list = []
    @l = l
    @r = r
    traverse(@head)
    @list
  end
end
```

```ruby
[6] pry(main)> b = Bst.new(10)
=> #<Bst:0x00007fb692335770 @head=#<Node:0x00007fb692335748 @left=nil, @right=nil, @val=10>, @list=[]>
[7] pry(main)> b.mktree
=> #<Node:0x00007fb6922eec80 @left=nil, @right=nil, @val=18>
[9] pry(main)> b.range_sum_bst(7,15)
=> [10, 7, 15]
```

## [distribute coins](https://leetcode.com/problems/distribute-coins-in-binary-tree/)

```ruby
class Node
  attr_accessor :val, :left, :right

  def initialize(val)
    @val = val
    @left = nil
    @right = nil
  end

  def add_left(val)
    self.left = Node.new(val)
  end

  def add_right(val)
    self.right = Node.new(val)
  end
end

class Bst # Bstじゃない・・Binary Treeだった
  def initialize(val)
    @head = Node.new(val)
    @list = []
  end

  def mktree
    @head.add_left(0)
    @head.left.add_right(3)
    @head.add_right(0)
  end

  def distribute_coins
    @result = 0
    dfs(@head)
    @result
  end

  def dfs(node)
    return 0 unless node
    left,right = dfs(node.left), dfs(node.right)
    @result += (left.abs + right.abs)
    p "node.val: #{node.val}, #{left} #{right}"
    return node.val + left + right - 1
  end
end
```

```ruby
[4] pry(main)> b=Bst.new(1)
=> #<Bst:0x00007fbc07428ce8 @head=#<Node:0x00007fbc07428cc0 @left=nil, @right=nil, @val=1>, @list=[]>
[5] pry(main)> b.mktree
=> #<Node:0x00007fbc068d7538 @left=nil, @right=nil, @val=0>
[6] pry(main)> b
=> #<Bst:0x00007fbc07428ce8
 @head=
  #<Node:0x00007fbc07428cc0
   @left=#<Node:0x00007fbc068d7588 @left=nil, @right=#<Node:0x00007fbc068d7560 @left=nil, @right=nil, @val=3>, @val=0>,
   @right=#<Node:0x00007fbc068d7538 @left=nil, @right=nil, @val=0>,
   @val=1>,
 @list=[]>
[7] pry(main)> cd b
[8] pry(#<Bst>):1> ls
Bst#methods: dfs  distribute_coins  mktree
self.methods: __pry__
instance variables: @head  @list
locals: _  __  _dir_  _ex_  _file_  _in_  _out_  _pry_
[11] pry(#<Bst>):1> ls
Bst#methods: dfs  distribute_coins  mktree
self.methods: __pry__
instance variables: @head  @list
locals: _  __  _dir_  _ex_  _file_  _in_  _out_  _pry_
[12] pry(#<Bst>):1> @result = 0
=> 0
[13] pry(#<Bst>):1> dfs(@head.left.right)
"node.val: 3, 0 0"
=> 2
[14] pry(#<Bst>):1> dfs(@head.left)
"node.val: 3, 0 0"
"node.val: 0, 0 2"
=> 1
[15] pry(#<Bst>):1> dfs(@head.right)
"node.val: 0, 0 0"
=> -1
[16] pry(#<Bst>):1> dfs(@head)
"node.val: 3, 0 0"
"node.val: 0, 0 2"
"node.val: 0, 0 0"
"node.val: 1, 1 -1"
=> 0
[17] pry(#<Bst>):1> ls
Bst#methods: dfs  distribute_coins  mktree
self.methods: __pry__
instance variables: @head  @list  @result
locals: _  __  _dir_  _ex_  _file_  _in_  _out_  _pry_
```