题目描述:

在一棵无限的二叉树上,每个节点都有两个子节点,树中的节点 逐行 依次按 “之” 字形进行标记。

如下图所示,在奇数行(即,第一行、第三行、第五行……)中,按从左到右的顺序进行标记;

而偶数行(即,第二行、第四行、第六行……)中,按从右到左的顺序进行标记。

tree.png

给你树上某一个节点的标号 label,请你返回从根节点到该标号为 label 节点的路径,该路径是由途经的节点标号所组成的。

示例:
输入:label = 14
输出:[1,3,4,14]

这道题刚看到,我其实是没有很多思路的,我在想,难不成要把树的结构给建出来然后用dfs算法来做吗?
想想觉得还是太过于笨重了,于是跑去评论区看了看,首先映入眼帘的就是牛逼的位运算解法,理解之后感觉真的是非常的奇妙。

解法一:

主要思路是这样的:首先,知道我们要找的数字label,因为二叉树的结构,每向下深入一层,实际上就是加上2的depth次幂,那么便有将label转换成二进制,向右移动一位,此时的最高位即为label的上一层的第一个数字,又因为该树状图是之字形排列,那么仅仅将其右移一位得到的并不是label的父节点,而是其父节点的对称位置的节点,那么如何才能得到父节点的数字呢?这时候就有一个精妙的操作,将除了最高位以外的所有位进行反转,这样便得到了当前数字的对称位置的数字。然后重复以上步骤便可以得到答案。

class Solution {
public:
    vector<int> pathInZigZagTree(int label) {
        vector<int> ans;
        while (label != 1) {
            ans.push_back(label);
            label >>= 1;
            //这里实际上就是获取当前label的二进制位数然后减1可以使得除最高位以外的所有数字为1,那么进行异或就 
            //会得到反转的效果
            label = label ^ (1 << ((int)log2(label))) - 1;
        }
        ans.push_back(1);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

解法二:

还有一种解法就是数学归纳法了,通过观察其实可以得到以下规律,label的父节点即为上一层的最后一个数减掉当前label到当前层数的第一个数的距离除以二。代码如下:

class Solution {
public:
    vector<int> pathInZigZagTree(int label) {
        int depth = log(label) / log(2);

        vector<int> ans;
        ans.push_back(label);
        for (int i = depth; i > 0; --i) {
            int edge = pow(2, i);
            label = edge - 1 - (label - edge) / 2;//核心语句
            ans.push_back(label);
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

最近刷一刷leetcode,感觉算法也不是那样的枯燥无味了,要坚持每天进步一点点,总有一天能跨过算法与数据结构的大关的

Last modification:August 20th, 2021 at 04:28 pm
如果觉得我的文章对你有用,请随意赞赏