[leetcode] 1104. Path In Zigzag Labelled Binary Tree

Description

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 = 14Output: [1,3,4,14]

Example 2:

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

Constraints:

1 <= label <= 10^6

分析

题目的意思是：找出给定结点在zigzag二叉树中到根结点的路径，这道题的难点在于公式推导，如果能够计算出来每个父节点的位置就好办了，递归求解父结点就可以了。怎么计算父结点的位置呢，可以首先把每一层最开始节点的编号求出来，即2^level，然后求出父结点到该层末数的个数：(label-corner)//2+1，由于父结点的编号跟当前节点的编号是相反的，所以最后编号：corner-1-th+1。可能也不是很明白，我这里写了一个可以debug的代码，可以debug感受一下过程。 比如n为14，那么其所在的层是3，2^3=8，第三层父结点到第四层相差的节点的个数：th为（14-8）//2+1=4，然后其所在的编号就是：corner-1-th+1=4.这样推算过来的。

代码

class Solution: def find_level(self,num): return math.floor(math.log(num,2)) def find_parent(self,label): level=self.find_level(label) corner=2**level th=(label-corner)//2+1 return corner-1-th+1 def pathInZigZagTree(self, label: int) -> List[int]: res=[label] while(True): label=self.find_parent(label) if(label>=1): res.append(label) else: return res[::-1]

代码二

import mathclass Solution: def __init__(self): super().__init__() self.corners=[] self.ths=[] def find_level(self,num): return math.floor(math.log(num,2)) def find_parent(self,label): level=self.find_level(label) corner=2**level th=(label-corner)//2+1 self.corners.append(corner) self.ths.append(th) return corner-1-th+1 def pathInZigZagTree(self, label): res=[label] while(True): label=self.find_parent(label) if(label>=1): res.append(label) else: return res[::-1] if __name__ == "__main__": solution=Solution() res=solution.pathInZigZagTree(14) print(res) print(solution.corners) print(solution.ths)

[1, 3, 4, 14][8, 4, 2, 1][4, 1, 1, 1]

参考文献

[1].Runtime: 24 ms, faster than 91.89% python. https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/discuss/629982/Runtime%3A-24-ms-faster-than-91.89-python

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。