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验证一下这个算法.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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; } }; |