Golang O(N*logN) solution, with a customized BST ( no TreeMap or similar things)

• The difficult part is how to merge the Nodes(ranges) if the adding value can connect two ranges.

``````type Node struct{
begin, end int
left, right *Node
}

type SummaryRanges struct {
root *Node
}

/** Initialize your data structure here. */
func Constructor() SummaryRanges {
return SummaryRanges{nil}
}

func mergeRightmost(toMerge , n *Node) *Node{
if n==nil{
toMerge.begin -= 1
return nil
}
if n.end + 2 == toMerge.begin{
toMerge.begin = n.begin
return n.left//remove n
}
n.right = mergeRightmost(toMerge, n.right)
return n
}

func mergeLeftmost(toMerge , n *Node) *Node{
if n==nil{
toMerge.end += 1
return nil
}
//fmt.Println("tomerge [", toMerge.begin, toMerge.end, "], @", n.begin)
if n.begin-2 == toMerge.end{
toMerge.end = n.end
return n.right//remove n
}
n.left = mergeLeftmost(toMerge, n.left)
return n
}

func add(n *Node, val int) *Node{
if n == nil{
return &Node{val,val, nil, nil}
}
//included
if  n.begin <= val && val <= n.end{
return n
}

//to insert left
if  val < n.begin{
if val +1 == n.begin{
n.left = mergeRightmost(n , n.left)
}else{
}
}else{//val > n.end
if val - 1 == n.end{
n.right = mergeLeftmost(n , n.right)
}else{
}
}
return n
}

func (this *SummaryRanges) Addnum(val int)  {
}

func  genInterval(n *Node, it []Interval ) []Interval {
if n == nil{
return it
}
it = genInterval(n.left, it)
it = append(it, Interval{n.begin, n.end} )
it = genInterval(n.right, it)
return it
}

func (this *SummaryRanges) Getintervals() []Interval {
return genInterval(this.root, make([]Interval,0))
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.