1104. 二叉树寻路

解法一

如果是正常顺序的二叉树，那么对于结点i，其父结点就是i/2。但是在本题中，是蛇形的顺序，因此父结点要换成在本层中的对称位置。知道每层的最大值和最小值，就可以算出其对称结点。
从底向上找父结点得到的倒序的结果，最后需要进行反转。

class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        int depth = (int)Math.floor(Math.log(label) / Math.log(2));
        // 树每一层的最小值和最大值
        int[][] table = new int[depth][2];
        for (int i = 0, x = 1; i < depth; x *= 2, ++i) {
            table[i][0] = x;
            table[i][1] = x * 2 - 1;
        }
        // 倒序添加路径上的点
        List<Integer> ans = new ArrayList<>(depth + 1);
        ans.add(label);
        for (int i = depth - 1; i >= 0; --i) {
            label = table[i][0] + table[i][1] - label / 2;
            ans.add(label);
        }
        // 翻转得到正序路径
        Collections.reverse(ans);
        return ans;
    }
}