发表于 2024.06.14

• 本质就是完全二叉树寻父节点计算方法(该计算在二叉堆里经常使用到，即，如果节点从1开始计数，则节点i的父节点为i // 2)的变体，只是这里的完全二叉树中，层次(从1开始计数)为偶数时，需要左右翻转过来编号。因此，可以先计算出当前节点的层次，然后根据层次的奇偶性，计算出当前节点的原始编号，再按原始的计算方法，根据原始编号计算出父节点的原始编号，然后再翻转回来即可，一直迭代到根节点即可。由于是镜面翻转，因此可以直接使用2 ** (level - 1) + 2 ** level - 1 - label来互转编号。

  class Solution:
      def transform(self, label: int) -> int:
          """ 原始label和zigzag label互转 """
          level = label.bit_length()
          if not level % 2:
              label = 2 ** (level - 1) + (2 ** level - 1 - label)
          return label
  
      def pathInZigZagTree(self, label: int) -> List[int]:
          ans = []
          while True:
              ans.append(label)
              if label == 1:  # 已经到达根节点
                  break
              orig_label = self.transform(label)
              # 按原始的完全二叉树计算法，计算指向父节点的原始label
              parent_orig_label = orig_label // 2
              # 将父节点的原始label恢复为zigzag label
              parent_zig_zag_label = self.transform(parent_orig_label)
              # label指向父节点
              label = parent_zig_zag_label
          ans.reverse()
          return ans

• LC 题目链接