package main
import(
"fmt"
"container/list"
)
func main(){
t := []interface{}{3, 9, 20, nil, nil, 15, 7}
r := NewBinaryTree(t)
a2 := Answer(r)
fmt.Println(a2)
}
type Node struct {
Value interface{}
Left *Node
Right *Node
}
func NewBinaryTree(btree []interface{}) *Node {
return newNode(btree, 0)
}
func newNode(btree []interface{}, idx int) *Node {
if (idx >= len(btree)) || (btree[idx] == nil) {
return nil
}
n := &Node{Value:btree[idx]}
n.Left = newNode(btree, idx*2+1)
n.Right = newNode(btree, idx*2+2)
return n
}
func Answer(node *Node) [][]interface{} {
q := list.New()
s := list.New()
q.PushBack(node)
q.PushBack(0)
max := 0
for q.Len() > 0 {
n := q.Front().Value.(*Node)
q.Remove(q.Front())
l := q.Front().Value.(int)
q.Remove(q.Front())
s.PushFront(n)
s.PushFront(l)
l++
max = l
if n.Left != nil {
q.PushBack(n.Left)
q.PushBack(l)
}
if n.Right != nil {
q.PushBack(n.Right)
q.PushBack(l)
}
}
var out [][]interface{}
for s.Len() > 0 {
l := s.Front().Value.(int)
s.Remove(s.Front())
n := s.Front().Value.(*Node)
s.Remove(s.Front())
i := max - l - 1
if i > len(out) - 1 {
out = append(out, []interface{}{})
}
out[i] = append(out[i], n.Value)
}
return out
}
cGFja2FnZSBtYWluCmltcG9ydCgKCSJmbXQiCgkiY29udGFpbmVyL2xpc3QiCikgCgoKZnVuYyBtYWluKCl7Cgl0IDo9IFtdaW50ZXJmYWNle317MywgOSwgMjAsIG5pbCwgbmlsLCAxNSwgN30KCXIgOj0gTmV3QmluYXJ5VHJlZSh0KQoJYTIgOj0gQW5zd2VyKHIpCglmbXQuUHJpbnRsbihhMikKfQoKdHlwZSBOb2RlIHN0cnVjdCB7CglWYWx1ZSBpbnRlcmZhY2V7fQoJTGVmdCAqTm9kZQoJUmlnaHQgKk5vZGUKfQoKZnVuYyBOZXdCaW5hcnlUcmVlKGJ0cmVlIFtdaW50ZXJmYWNle30pICpOb2RlIHsKCXJldHVybiBuZXdOb2RlKGJ0cmVlLCAwKQp9CgpmdW5jIG5ld05vZGUoYnRyZWUgW11pbnRlcmZhY2V7fSwgaWR4IGludCkgKk5vZGUgewoJaWYgKGlkeCA+PSBsZW4oYnRyZWUpKSB8fCAoYnRyZWVbaWR4XSA9PSBuaWwpIHsKCQlyZXR1cm4gbmlsCgl9CgoJbiA6PSAmTm9kZXtWYWx1ZTpidHJlZVtpZHhdfQoJbi5MZWZ0ID0gbmV3Tm9kZShidHJlZSwgaWR4KjIrMSkKCW4uUmlnaHQgPSBuZXdOb2RlKGJ0cmVlLCBpZHgqMisyKQoKCXJldHVybiBuCn0KCmZ1bmMgQW5zd2VyKG5vZGUgKk5vZGUpIFtdW11pbnRlcmZhY2V7fSB7CglxIDo9IGxpc3QuTmV3KCkKCXMgOj0gbGlzdC5OZXcoKQoJcS5QdXNoQmFjayhub2RlKQoJcS5QdXNoQmFjaygwKQoJbWF4IDo9IDAKCglmb3IgcS5MZW4oKSA+IDAgewoJCW4gOj0gcS5Gcm9udCgpLlZhbHVlLigqTm9kZSkKCQlxLlJlbW92ZShxLkZyb250KCkpCgkJbCA6PSBxLkZyb250KCkuVmFsdWUuKGludCkKCQlxLlJlbW92ZShxLkZyb250KCkpCgoJCXMuUHVzaEZyb250KG4pCgkJcy5QdXNoRnJvbnQobCkKCgkJbCsrCgkJbWF4ID0gbAoJCWlmIG4uTGVmdCAhPSBuaWwgewoJCQlxLlB1c2hCYWNrKG4uTGVmdCkKCQkJcS5QdXNoQmFjayhsKQoJCX0KCQlpZiBuLlJpZ2h0ICE9IG5pbCB7CgkJCXEuUHVzaEJhY2sobi5SaWdodCkKCQkJcS5QdXNoQmFjayhsKQoJCX0KCX0KCgl2YXIgb3V0IFtdW11pbnRlcmZhY2V7fQoJZm9yIHMuTGVuKCkgPiAwIHsKCQlsIDo9IHMuRnJvbnQoKS5WYWx1ZS4oaW50KQoJCXMuUmVtb3ZlKHMuRnJvbnQoKSkKCQluIDo9IHMuRnJvbnQoKS5WYWx1ZS4oKk5vZGUpCgkJcy5SZW1vdmUocy5Gcm9udCgpKQoKCQlpIDo9IG1heCAtIGwgLSAxCgkJaWYgaSA+IGxlbihvdXQpIC0gMSB7CgkJCW91dCA9IGFwcGVuZChvdXQsIFtdaW50ZXJmYWNle317fSkKCQl9CgoJCW91dFtpXSA9IGFwcGVuZChvdXRbaV0sIG4uVmFsdWUpCgl9CgoJcmV0dXJuIG91dAp9