零壹塔（力扣,递归，找父节点）

https://leetcode.cn/problems/k-th-symbol-in-grammar/

0
/ \
0 1
/ \ /
0 1 1 0
/ \ / \ / \ / \
0 1 1 0 1 0 0 1

#include<iostream> using namespace std; int solve(int n, int k) { if (n == 1)return 0; //如果不是第一层则寻找父节点n=n-1,k+1/2 else { int father=solve(n - 1, k + 1>>1); //如果k是奇数，则他等于他的父节点，如果k是偶数，则他等于父节点取反 return (k & 1) == 1 ? father : 1 ^ father; } } int main() { int n, k; cin >> n >> k; cout << solve(n, k) << endl; return 0; }
简化一下
#include<iostream> using namespace std; int solve(int n, int k) { return n == 1 ? 0 : solve(n - 1, k + 1 >> 1) ^ (k & 1) ^ 1; } int main() { int n, k; cin >> n >> k; cout << solve(n, k) << endl; return 0; }