Advertisement
Inverth

Untitled

Aug 7th, 2022 (edited)
883
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Go 1.90 KB | None | 0 0
  1. package main
  2.  
  3. import (
  4.     "fmt"
  5.     "strings"
  6. )
  7.  
  8. type TreeNode struct {
  9.     Val   int
  10.     Left  *TreeNode
  11.     Right *TreeNode
  12. }
  13.  
  14. var path []int
  15. var output []string
  16.  
  17. func BinaryTreePaths(head *TreeNode) []string {
  18.     if nil == head {
  19.         return make([]string, 0)
  20.     }
  21.  
  22.     path = make([]int, 0, 5)
  23.     output = make([]string, 0, 5)
  24.  
  25.     walk(head)
  26.  
  27.     return output
  28. }
  29.  
  30. func walk(curNode *TreeNode) {
  31.     if 0 != curNode.Val {
  32.         path = append(path, curNode.Val)
  33.     }
  34.  
  35.     if nil != curNode.Left {
  36.         walk(curNode.Left)
  37.     }
  38.  
  39.     if nil != curNode.Right {
  40.         walk(curNode.Right)
  41.     }
  42.  
  43.     if nil == curNode.Left && nil == curNode.Right {
  44.         output = append(output, generateOutput("->"))
  45.     }
  46.     path = deleteLastElement(path)
  47. }
  48.  
  49. func deleteLastElement(slice []int) []int {
  50.     if len(slice) > 0 {
  51.         return slice[:len(slice)-1]
  52.     }
  53.  
  54.     return make([]int, 0, 5)
  55. }
  56.  
  57. func generateOutput(delim string) string {
  58.     return strings.Trim(strings.Join(strings.Split(fmt.Sprint(path), " "), delim), "[]")
  59. }
  60.  
  61. func CreateNode(val int, left *TreeNode, right *TreeNode) *TreeNode {
  62.     var node TreeNode
  63.     node.Val = val
  64.     node.Left = left
  65.     node.Right = right
  66.  
  67.     return &node
  68. }
  69.  
  70. func InitNode(val int) *TreeNode {
  71.     return CreateNode(val, nil, nil)
  72. }
  73.  
  74. func arrayToTree(data []int) *TreeNode {
  75.     var count = len(data)
  76.     if count == 0 {
  77.         return nil
  78.     }
  79.  
  80.     var head = InitNode(data[0])
  81.     var curNode = head
  82.  
  83.     for i := 1; i < count; {
  84.         if i < count && data[i] != 0 {
  85.             curNode.Left = InitNode(data[i])
  86.         } else {
  87.             curNode.Left = nil
  88.         }
  89.  
  90.         i += 1
  91.  
  92.         if i < count && data[i] != 0 {
  93.             curNode.Right = InitNode(data[i])
  94.         } else {
  95.             curNode.Right = nil
  96.         }
  97.  
  98.         i += 1
  99.  
  100.         if curNode.Left != nil && curNode.Left.Val != 0 {
  101.             curNode = curNode.Left
  102.         } else {
  103.             curNode = curNode.Right
  104.         }
  105.     }
  106.  
  107.     return head
  108. }
  109.  
  110. func main() {
  111.     var head = arrayToTree([]int{1, 2, 3, 0, 5})
  112.     var res = BinaryTreePaths(head)
  113.  
  114.     fmt.Printf("%v, ", res)
  115. }
  116.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement