leetcode 1104
Published:
题目1104
在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。
输入样例
输入：label = 14 输出：[1,3,4,14]
解析
所谓之字形树，就是把一个顺序的二叉树在奇数行将行内元素反转。这种反转实际上可以用一个变换函数来转为反转后元素，那只要正常输出元素，然后在奇数行内对元素执行一次变化即可。
题解
class Solution:
def setrever(self,val,high):
import math
end=math.pow(2,high)
start=end//2
return int(end-val+start-1)
def pathInZigZagTree(self, label: int) -> List[int]:
import math
level=int(math.log2(label))+1
trueval=label
if level%2==0:
trueval=self.setrever(label,level)
result=[label]
while level>1:
level-=1
trueval=int(trueval//2)
if level%2==0:
result=[self.setrever(trueval,level)]+result
else:
result=[trueval]+result
return result