LeetCode题解:Path In Zigzag Labelled Binary Tree

本文为LeetCode 1104. Path In Zigzag Labelled Binary Tree 的题解。

题目描述

一棵无穷的二叉树,每个节点都编号(label)了:对于奇数层(第1、3、5等层),从左向右编号。对于偶数层,从右向左编号。但是每层的编号还是最小2^(level-1),最大2^level-1

如图:

给你一个编号(label),输出从顶层到该节点经过的节点编号。

Example 1:

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

Example 2:

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

思路

  1. 给定节点,我们可以知道节点在第几层
  2. 给定正常树中的编码,可以知道父节点的编号。
  3. 给定正常树中的编码,可以知道在该变异树中的节点编号。

第一点是显而易见的,log(label)即为层数。

第二点,正常节点的值label除以2即为父节点的label。

对于第三点,在level层,变异树中的节点label和正常树的节点label(也就是树中堆成位置的节点)之和为2^(level-1)*3-1

比如图中第四层,14节点在正常编码的时候是9,14+9=2^(4-1)*3-1=23

这样,我们只需要在正常树中向上回溯到根节点就好,只是在放结果的时候,转化为变异树的label值即可。

代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.Arrays;
import java.util.List;

/**
* https://www.robberphex.com/path-in-zigzag-labelled-binary-tree/
*/
class Solution {
/**
* 计算label节点在第几层
*/
private int level(int label) {
int level = 0;
while (label != 0) {
level += 1;
label >>= 1;
}
return level;
}

/**
* 计算第level层的label节点变换后的位置
* <p>
* 如果输入变异节点,则输出正常节点
* 反之亦然
*/
private int normalLabel(int label, int level) {
if (level % 2 == 0) {
int base = 1 << (level - 1);
int sum = base * 3 - 1;
label = sum - label;
}
return label;
}

public List<Integer> pathInZigZagTree(int label) {
int totelLevel = level(label);
Integer[] res = new Integer[totelLevel];

// 我们需要在正常树中回溯
// 故先将输入节点替换为正常树中的节点
label = normalLabel(label, totelLevel);

// 树的回溯
while (label != 0) {
int level = level(label);
res[level - 1] = normalLabel(label, level);
label /= 2;
}
return Arrays.asList(res);
}

public static void main(String[] args) {
List<Integer> res = new Solution().pathInZigZagTree(33);
System.out.println(res);
// 输出 [1, 2, 7, 8, 31, 33]
}
}

LeetCode题解:Path In Zigzag Labelled Binary Tree

https://robberphex.com/path-in-zigzag-labelled-binary-tree/

作者

Robert Lu

发布于

2019-06-30

许可协议

评论