首页 > itarticle > leetcode 1104.path in zigzag labelled binary tree Solution

leetcode 1104.path in zigzag labelled binary tree Solution

admin 1月 21, 2021 0

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.

tree.png

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:

1
2
 
Input: label = 14
Output: [1,3,4,14]

Example 2:

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

Constraints:

1
 
1 <= label <= 10^6

Solution

首先根据label计算所在行数，根据行数奇偶可以判断这一行的数是否逆序。逆序则计算正序时对应的值，然后//2得到上一层正序时的值，再判断上一层层数的奇偶性，若上一层是偶数层，则将数字转换为逆序时的值。重复此过程直到根节点。

Python:

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
 
import math
class :
    def findOriginIndex(self, label):
        row = math.floor(math.log(label, 2) + 1)
        rowMin = pow(2, row - 1) 
        rowMax = pow(2, row) - 1
        sm = rowMin + rowMax
        return sm - label
    def pathInZigZagTree(self, label: int):
        if label == 1:
            return [1]
        ret = []
        ret.append(label)
        while label != 1:
            row = math.floor(math.log(label, 2) + 1)
            if row & 1 == 0:
                label = self.findOriginIndex(label)
                label >>= 1
                ret.append(label)
                continue
            label >>= 1
            label = self.findOriginIndex(label)
            ret.append(label)
        ret.reverse()
        return ret

Java:

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
28
29
30
31
32
33
 
import java.util.ArrayList;
import java.util.List;

class  {
    public int originIndex(int label){
        int row = (int) Math.floor(Math.log(label) / Math.log(2) + 1);
        int rowMin = (int) Math.pow(2, row - 1);
        int rowMax = (int) (Math.pow(2,row) - 1);
        int sm = rowMin + rowMax;
        int ret = sm - label;
        return ret;
    }
    public List<Integer> pathInZigZagTree(int label) {
        List<Integer> ret = new ArrayList<Integer>();
        ret.add(label);
        if (1 == label) {
            return ret;
        }
        while (label != 1) {
         int row = (int) Math.floor(Math.log(label) / Math.log(2) + 1);
         if ((row & 1) == 0) {
               label = this.originIndex(label);
                label = label >> 1;
                ret.add(0, label);
               continue;
           }
            label = label >> 1;
            label = this.originIndex(label);
            ret.add(0,label);
        }
        return ret;
    }
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能