【数学】1104. 二叉树寻路（中等）
让我们先来看看这道题目的描述
因为题目给出的是完全二叉树，所以我们可以用数学技巧来实现，当偶数行时，label是从右向左排列的，而当奇数行时，label是从左向右排列的。
如果不考虑奇偶性，都按照从左到右的顺序，一个节点的两个子节点的值分别为val * 2 ， val * 2 + 1，有比较强的规律
所以我们将偶数行的值先按照正常顺序排列，再计算得到真正的值
一个偶数行的数值真正的情况应该为 2 ^ 行数 - 1 + 2 ^ 行数 - 1 - val
private int reverse(int val, int depth){return (1 << depth - 1) + (1 << depth) - 1 - val;}
class Solution{public List<Integer> pathInZigZagTree(int label) {List<Integer> ans = new ArrayList<>();int depth = findDepth(label);if (depth % 2 == 0) {label = reverse(label, depth);}while(depth > 0){if(depth % 2 != 0){ans.add(label);}else{ans.add(reverse(label, depth));}depth--;label >>= 1;}Collections.reverse(ans);return ans;}private int findDepth(int val){int depth = 0;while(val >= 1){val >>= 1;depth++;}return depth;}private int reverse(int val, int depth){return (1 << depth - 1) + (1 << depth) - 1 - val;}}
如果计算出的总行数为偶数，需要先对这个label值进行操作，否则会发生错误。也可以把这一行单独拿出来讨论～