1104. Path In Zigzag Labelled Binary Tree

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

在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。

如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；

而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。

给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。

示例 1：

输入：label = 14
输出：[1,3,4,14]

示例 2：

输入：label = 26
输出：[1,2,6,10,26]

思路： 数学计算，先计算出深度，再自下而上计算每一层的数字。由于满二叉树的性质，可以容易计算出，每一层的数字范围[2^i-1 , 2ⁱ-1] , 满二叉树，节点 j 的父节点是 j/2 , 由于逆序，所以 j 的父节点 = 2^i-1 + 2ⁱ-1 - j/2;

/**
* 1. 计算出深度
* 2. 求父节点不逆序的位置i，计算出一层从的开头a和结尾b的位置， 得到实际位置 a+b-i
**/
class Solution {
    public List<Integer> pathInZigZagTree(int label) {

        int depth = 1;
        while(label >=  (1<<depth) ){
            depth++;
        }

        List<Integer> ret = new ArrayList<>();
        ret.add(0,label);
        depth--;
        while(depth >= 1) {
            int end =  (1 <<depth)-1;
            int start = 1 <<(depth-1);
            int parent = (end+start) - (label / 2);
            label = parent;
            ret.add(0, parent);
            depth--;
        }
        return ret;
    }
}