Path In Zigzag Labelled Binary Tree

给一个二叉树, 里面的label是zigzag的, 给一个val, 求val到root路径.

这题看似求路径, 实测是二进制的题,因为是zigzag的. 所以从val本身出发看, 比如val是例题的14, 那么14的二进制是1110, 14上一个node是4, 4的二进制是100, 可以看出规律是 1110 先右移 变成111, 然后翻转除了第一个digit外的所有digit. 可以随便拿别的node验证一下这个算法.

class Solution {
public:
    vector<int> pathInZigZagTree(int label) {
        vector<int> res;
        while(label > 0){
            res.push_back(label);
            int m = (int)log2(label); // m是label的二进制位数-1
            for(int i = 0; i < m; i++) {
                label = (label ^ (1 << i)); //flip
            }
            label = label >> 1;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};