Golang solution, serialization of two trees


  • 0

    It's a tricky problem for me.
    First trap is we can't ignore "nil" node otherwise different tree will be regarded as same.
    Second, we need to handle the case like s = [12, 1], t = [2, 1] .
    The condition

    if found == 0 || sstr[found-1] == '|'
    

    was set to ignore this. Otherwise serialized s "12|1" contains t "2|1" so it will return true.

    func isSubtree(s *TreeNode, t *TreeNode) bool {
    	if s == nil {
    		return t == nil
    	}
    
    	sb, tb := &bytes.Buffer{}, &bytes.Buffer{}
    	buildString(s, sb)
    	buildString(t, tb)
    	sstr, tstr := sb.String(), tb.String()
    
    	if found := strings.Index(sstr, tstr); found != -1 {
    		if found == 0 || sstr[found-1] == '|' {
    			return true
    		}
    		sstr = sstr[found+1:]
    	}
    	return false
    }
    
    func buildString(t *TreeNode, b *bytes.Buffer) {
    	if t == nil {
    		if b.Len() == 0 {
    			b.WriteString("_") // nil => '_'
    		} else {
    			b.WriteString("|_") // separator => '|'
    		}
    		return
    	}
    
    	valstr := strconv.Itoa(t.Val)
    	if b.Len() == 0 {
    		b.WriteString(valstr)
    	} else {
    		b.WriteString("|" + valstr)
    	}
    	buildString(t.Left, b)
    	buildString(t.Right, b)
    }
    
    

Log in to reply
 

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