# Leetcode 779. K-th Symbol in Grammar ![](https://hackmd.io/_uploads/HJYLnjUzT.png) 觀察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 的點 ![](https://hackmd.io/_uploads/H1uCQhUfT.png)