鏈接：https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/

package leetcode

import (
    "math"
)

func PathInZigZagTree(label int) []int {
    if label == 1 {
        return []int{1}
    }
    rangeMap := make(map[int][]int, 0) //得到每層的最小值和最大值
    n := 1                             //樹的高度
    for {
        min := int(math.Pow(2, float64(n-1)))   //當(dāng)前層的最小值
        max := int(math.Pow(2, float64(n)) - 1) //當(dāng)前層的最大值
        rangeMap[n] = []int{min, max}
        if label >= min && label <= max {
            break
        }
        n++
    }

    //判斷是否為偶數(shù)
    var isEvenNumber func(a int) bool
    isEvenNumber = func(a int) bool {
        if a%2 == 0 {
            return true
        }
        return false
    }

    num := label
    var list []int
    list = append(list, label)
    for n > 1 {
        min := rangeMap[n][0]
        max := rangeMap[n][1]
        var pos int
        if isEvenNumber(n) {
            pos = (max - num) / 2        //父節(jié)點的位置
            num = rangeMap[n-1][0] + pos //父節(jié)點的值
        } else {
            pos = (num - min) / 2        //父節(jié)點的位置
            num = rangeMap[n-1][1] - pos //父節(jié)點的值
        }
        n--
        list = append(list, num)
    }

    //反轉(zhuǎn)list
    for i, j := 0, len(list)-1; i < j; i, j = i+1, j-1 {
        list[i], list[j] = list[j], list[i]
    }

    return list
}