LeetCode·每日一题·779.第K个语法符合·递归

链接：https://leetcode.cn/problems/k-th-symbol-in-grammar/solutions/1906588/di-gui-zhu-shi-chao-ji-xiang-xi-by-xun-g-qsjj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处 

题目

 

示例

 

思路

先做出前几行的图看一看，可以生成如下一棵满二叉树：

 其实每一行都可以生成一个满二叉树。

可以看出，某一个位置是1还是0：

• 取决于他的父亲
• 和他本身是left还是right。

假如是左孩子，就与父亲相同；否则与父亲相反。

所以，我们要判断某一个位置，就要先求它的父亲，然后根据位置判断是否取反即可。

可以采用递归：如果是第一层，直接返回0，否则求它的父亲。(n,k)的父亲的位置，就是(n-1,(k+1)/2)，解释一下为什么 k 的父节点是 (k+1)/2 ：

当我们用数组来存储一个树时：

当前节点 为 k，那么其左孩子节点为 k2 + 1, 其右孩子为 k2 + 2，这个也是为什么可以通过奇偶判断当前位置是左孩子还是右孩子

那么已知 当前位置 为 k，求当前位置的父节点这个就很容易了， 设 x 为父节点 x*2 + 1 = k 那么 x = (k-1)/2，如果k为 右孩子的话 x = (k-2)/2，因为会向下取整所以 x=(k-1)/2，这里就有人好奇了怎么和(k+1)/2不一样呀？其实这个是因为我们上述条件都是以起始坐标为 0 的情况，而且题目给定的是 k 从 1 开始，所以上述就需要改为 (x-1)*2 + 1 = k，所以 x = (k-1)/2 + 2 -> (k+1)/2 ;

而某个位置是左孩子还是右孩子，可以判断k是否为奇数：

• 如果是奇数，就是左孩子，那就应该与父亲相同，否则相反。

可以通过对 2 取余判断奇偶性：

• 如果是奇数，k%2==1，否则k%2==0。

代码

class Solution {
public:
    int kthGrammar(int n, int k) {
        if(n == 0) return 0;
        int ret = kthGrammar(n-1, (k+1) / 2);//求父节点值
        if(k % 2 == 1)//当前节点为 左孩子还是右孩子
        {
            return ret == 0 ? 0 : 1;
        }
        else
        {
            return ret == 0 ? 1 : 0; 
        }
    }
};
 
作者：小迅
链接：https://leetcode.cn/problems/k-th-symbol-in-grammar/solutions/1906588/di-gui-zhu-shi-chao-ji-xiang-xi-by-xun-g-qsjj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 
int kthGrammar(int n, int k){
    if(n == 1) return 0;
    int ret = kthGrammar(n-1, (k+1)/2);//求父节点值
    if(k % 2 == 1)//当前节点为 左孩子还是右孩子
    {
        return ret == 0 ? 0 : 1;
    }
    else
    {
        return ret == 0 ? 1 : 0;
    }
    return 0;
}
 
作者：小迅
链接：https://leetcode.cn/problems/k-th-symbol-in-grammar/solutions/1906588/di-gui-zhu-shi-chao-ji-xiang-xi-by-xun-g-qsjj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。