# [779. K-th Symbol in Grammar](https://leetcode.com/problems/k-th-symbol-in-grammar/description/)
## 1. 題目說明
- **有一個列表，初始化為 ==`'0'`==**
- **每次會生成一個新的列**
- **生成規則：**
1. **表中只有兩種符號 ==`'0'、'1'`==**
2. **對於列表中的所有符號，**
- **若該符號為 ==`'0'`==，則將該符號變成 ==`"01"`==**
- **若該符號為 ==`'1'`==，則將該符號變成 ==`"10"`==**
- **ex：`"01"` => `"0110"`**
- **ex：`"0110"` => `"01101001"`**
- **使用者輸入參數 ==`n、k`==**
- **要索引表中==第 n 列==的==第 k 個==符號，並輸出**
## 2. 解題思路1(二元樹搜索)
- **把每次的生成結果記錄下來**
- **假設==往左子樹==的方向設為 ==`'0'`==**
- **假設==往右子樹==的方向設為 ==`'1'`==**

flowchart
 n1([row 1]) -->
 n2([row 2]) -->
 n3([row 3]) -->
 n4([row 4]) 
 a1([0]) --0--> b1([0])
 a1 --1--> b2([1])
 b1 --00--> c1([0])
 b1 --01--> c2([1])
 b2 --10--> c3([1])
 b2 --11--> c4([0])
 c1 --000--> d1([0])
 c1 --001--> d2([1])
 c2 --010--> d3([1])
 c2 --011--> d4([0])
 c3 --100--> d5([1])
 c3 --101--> d6([0])
 c4 --110--> d7([0])
 c4 --111--> d8([1])

1. **==左子節點==的==符號不變==**
2. **==右子節點==的==符號反向==**
3. **==第 k 個==符號的 ==index = k - 1==**
4. **==第 n 列==的符號串會繼承至==n + 1 列==的左半邊**
- **ex：**
- **`row 2 = "01"`**
- **`row 3 = "0110"`**
- **`row 4 = "01101001"`**
5. **所以==第 n 列==的==第 k 個==符號，與==第 n + x 列==的==第 k 個==相同**
- **==x > 0==**
### ● 程式碼

int kthGrammar(int n, int k) {
    bool ans = 0;//初始符號為0
    k--;
    while (k > 0) {
        //右子節點為1，符號反向
        //反之不變
        if (k % 2 == 1)
            ans = !ans;
        k /= 2;
    }
    return (int)ans;
}

---