golang刷leetcode 技巧（4）二叉树寻路
golang刷leetcode 技巧（4）二叉树寻路
golangLeetcode
发布于 2022-08-02 18:37:14
发布于 2022-08-02 18:37:14
文章被收录于专栏：golang算法架构leetcode技术php
在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。
示例 1：
输入：label = 14
输出：[1,3,4,14]示例 2：
输入：label = 26
输出：[1,2,6,10,26]提示：
1 <= label <= 10^6
解题思路
1，没有限制，其实就是一棵完全二叉树
2，完全二叉树的性质：
正常得满二叉树编码方式，根节点index是1，那假设父节点index是n，那左子树节点是2 * n， 右子树 2 * n + 1
3，在不zigzag 的基础上给二叉树编号，我们可以很容易得到路径。label／2 直到根节点
4，考虑zigzag，分两种情况
A，label 在偶数层，这种不需要处理
B，label在奇数层，需要在当前层做镜像处理。
5，等到原始路径后，除了根和最后一层，中间层分两种情况。
A，label 在偶数层，这种不需要处理
B，label在奇数层，需要在当前层做镜像处理。
代码实现
func pathInZigZagTree(label int) []int {
var path []int
h:=height(label)
rl:=label
if h%2==1{
row:=getRow(h)
index:=0
for i:=0;i<len(row);i++{
if row[i]==label{
index=i
break
}
}
rl=row[len(row)-1-index]
}
for rl>0{
path=append([]int{rl},path...)
rl/=2
}
path[len(path)-1]=label
//fmt.Println(path)
for i:=1;i<len(path)-1;i++{
index:=0
row:=getRow(i)
for k:=0;k<len(row);k++{
if row[k]==path[i]{
index=k
break
}
}
if i%2==1{
path[i]=row[len(row)-1-index]
fmt.Println(index,row,path[i],i,len(row)-1-index)
}
}
return path
}
func pow(x,y int)int{
z:=1
for i:=0;i<y;i++{
z*=x
}
return z
}
func height(x int)int{
i:=0
for x>0{
i++
x/=2
}
return i-1
}
func getRow(i int)[]int{
var row []int
for j:=pow(2,i);j<pow(2,i+1);j++{
row=append(row,j)
}
//fmt.Println(row)
return row
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-02-09，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读
腾讯云开发者
