fork(1) download
copy 
  1. package main
  2. import(
  3. 	"fmt"
  4. 	"container/list"
  5. ) 
  6.  
  7.  
  8. func main(){
  9. 	t := []interface{}{3, 9, 20, nil, nil, 15, 7}
  10. 	r := NewBinaryTree(t)
  11. 	a2 := Answer(r)
  12. 	fmt.Println(a2)
  13. }
  14.  
  15. type Node struct {
  16. 	Value interface{}
  17. 	Left *Node
  18. 	Right *Node
  19. }
  20.  
  21. func NewBinaryTree(btree []interface{}) *Node {
  22. 	return newNode(btree, 0)
  23. }
  24.  
  25. func newNode(btree []interface{}, idx int) *Node {
  26. 	if (idx >= len(btree)) || (btree[idx] == nil) {
  27. 		return nil
  28. 	}
  29.  
  30. 	n := &Node{Value:btree[idx]}
  31. 	n.Left = newNode(btree, idx*2+1)
  32. 	n.Right = newNode(btree, idx*2+2)
  33.  
  34. 	return n
  35. }
  36.  
  37. func Answer(node *Node) [][]interface{} {
  38. 	q := list.New()
  39. 	s := list.New()
  40. 	q.PushBack(node)
  41. 	q.PushBack(0)
  42. 	max := 0
  43.  
  44. 	for q.Len() > 0 {
  45. 		n := q.Front().Value.(*Node)
  46. 		q.Remove(q.Front())
  47. 		l := q.Front().Value.(int)
  48. 		q.Remove(q.Front())
  49.  
  50. 		s.PushFront(n)
  51. 		s.PushFront(l)
  52.  
  53. 		l++
  54. 		max = l
  55. 		if n.Left != nil {
  56. 			q.PushBack(n.Left)
  57. 			q.PushBack(l)
  58. 		}
  59. 		if n.Right != nil {
  60. 			q.PushBack(n.Right)
  61. 			q.PushBack(l)
  62. 		}
  63. 	}
  64.  
  65. 	var out [][]interface{}
  66. 	for s.Len() > 0 {
  67. 		l := s.Front().Value.(int)
  68. 		s.Remove(s.Front())
  69. 		n := s.Front().Value.(*Node)
  70. 		s.Remove(s.Front())
  71.  
  72. 		i := max - l - 1
  73. 		if i > len(out) - 1 {
  74. 			out = append(out, []interface{}{})
  75. 		}
  76.  
  77. 		out[i] = append(out[i], n.Value)
  78. 	}
  79.  
  80. 	return out
  81. }
Success #stdin #stdout 0s 2984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[[7 15] [20 9] [3]]
https://ideone.com/Cnw1Up
language:
Go (go 1.12.1)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!