JZX轻语：简

LeetCode 1104 - 二叉树寻路

发表于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

题目链接：https://leetcode.cn/problems/path-in-zigzag-labelled-binary-tree/