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


  • 0
    F

    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{
                n.left = add(n.left, val)
            }
        }else{//val > n.end
            if val - 1 == n.end{
                n.right = mergeLeftmost(n , n.right)
            }else{
                n.right = add(n.right, val)
            }
        }
        return n
    }
    
    func (this *SummaryRanges) Addnum(val int)  {
        this.root = add(this.root, val)
    }
    
    
    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))
    }
    
    

Log in to reply
 

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