之字形标记

1104. 二叉树寻路

思路

思路其实很清晰,翻转出层序的下标,在遍历的时候,把层序下标翻转回之字下标即可。

良好的编程习惯其实蛮重要的,每个变量都有自己的用处。良好的代码对后续的修改友善的。

代码


class Solution {
public:
    vector<int> pathInZigZagTree(int label) {
        vector<int> labels;
        int level = 0;
        int toggle = label;
        while(toggle) {
            toggle /= 2;
            level++;
        }

        int real = label;
        if((level & 1) == 0) {
            real = reverted(label, level--);
            real /= 2;
            labels.push_back(label);
        }
        while(level > 0) {
            if((level & 1) != 1) {
                label = reverted(real, level); 
            } else label = real;
            
            labels.push_back(label);
            level--;
            real /= 2;
        }
        reverse(labels.begin(), labels.end());
        return labels;
    }

    int reverted(int num, int level) {
        return pow(2, level) -  1 - (num - pow(2, level - 1));
    }
};
// 14 7 3 1 
// 

Comments