1104. Path in Zigzag Labelled Binary Tree

# 1104. Path In Zigzag Labelled Binary Tree#

## 题目 #

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.

Given the `label` of a node in this tree, return the labels in the path from the root of the tree to the node with that `label`.

Example 1:

``````Input: label = 14
Output: [1,3,4,14]

``````

Example 2:

``````Input: label = 26
Output: [1,2,6,10,26]

``````

Constraints:

• `1 <= label <= 10^6`

## 解题思路 #

• 计算出 label 所在的 level 和 index。
• 根据 index 和 level 计算出父节点的 index 和 value。
• level 减一，循环计算出对应的父节点直到根节点。

## 代码 #

``````package leetcode

func pathInZigZagTree(label int) []int {
level := getLevel(label)
ans := []int{label}
curIndex := label - (1 << level)
parent := 0
for level >= 1 {
parent, curIndex = getParent(curIndex, level)
ans = append(ans, parent)
level--
}
ans = reverse(ans)
return ans
}

func getLevel(label int) int {
level := 0
nums := 0
for {
nums += 1 << level
if nums >= label {
return level
}
level++
}
}

func getParent(index int, level int) (parent int, parentIndex int) {
parentIndex = 1<<(level-1) - 1 + (index/2)*(-1)
parent = 1<<(level-1) + parentIndex
return
}

func reverse(nums []int) []int {
left, right := 0, len(nums)-1
for left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
return nums
}
``````

Apr 8, 2023