链接：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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。