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值即可。

代码

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]
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.