Leetcode 779. K-th Symbol in Grammar

觀察row狀態

row 1                 0
row 2         0                1
row 3     0       1        1        0
row 4   0   1   1   0    1   0    0   1

可看成一個二元樹
根據規則
0的左節點0 , 右節點1
1的左節點1 , 右節點0

可知
如果是左節點跟 parent 相同
如果是右節點跟 parent 相異

再把每個row的點編號用１-indexed base來看

row 1                 1
row 2         1                2
row 3     1       2        3        4
row 4   1   2   3   4    5   6    7   8

如果你是偶數則為右節點
如果你是奇數則為左節點

假設今天要你找 n=2 , k=2
k=2 偶數 => 右節點 -> parent 的index 為 k/2
而且與parent 的值相異
遞迴就是找上一層 n=1 , k=1 的點然後 xor 1

如果今天是找 n=2 , k=1
k=1 奇數 => 左節點 -> parent 的index 為 (k+1)/2
而且與parent 的值相同
遞迴就是找上一層 n=1 , k=1 的點