【二叉树-中等】1104. 二叉树寻路

【题目】
【代码】

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        parents=[]
        levels=[]
        def levelVisit(label):
            nonlocal levels
            for level_id in range(1,1001):
                level=[pow(2,level_id)+i for i in range(pow(2,level_id))]
                levels.append(level)
                if label in level:
                    break
            levels=levels[::-1]
            # print(levels)
            for idx,level in enumerate(levels):
                parents.append(label)
                if label not in levels[idx]:
                    break
                cur_pos=levels[idx].index(label)//2
                # print("idx:",idx," cur_pos:",cur_pos)
                if idx!=len(levels)-1:
                    label=levels[idx+1][len(levels[idx+1])-1-cur_pos]
        if label==1:
            return [1]
        levelVisit(label)
        parents.append(1)
        # print(parents)
        return parents[::-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

【方法2】来自麦麦麦麦子。的题解

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        res = []
        while label != 1:
            res.append(label)
            label >>= 1
            label = label ^(1 << (label.bit_length() - 1)) - 1
        return [1]+res[::-1]
1
2
3
4
5
6
7
8