LeetCode 779 938

779. 第K个语法符号

在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。

给定行数 N 和序数 K，返回第 N 行中第 K个字符。（K从1开始）

例子:

输入: N = 1, K = 1
输出: 0

输入: N = 2, K = 1
输出: 0

输入: N = 2, K = 2
输出: 1

输入: N = 4, K = 5
输出: 1

解释:
第一行: 0
第二行: 01
第三行: 0110
第四行: 01101001

这是递归类的题目，首先对特殊情况进行分析第一行和第二行 第一行的话 直接返回0 第二行的话只有两个可能0 或者 1 不像从第三行开始，因为K有四个所以可能的情况也很多，但是归根结底，研究题上给出的从第一行到第四行的规律来看，可把除第一行以外的所有行数字从中间一切两半分为两部分，右半部分的每个数字为左半部分对应位置上数字的取反。
所以这个时候只需要判断K值大小 如果K > N / 2 那么进行递归取反即可 其他情况直接递归至 N-1 即可
还有一个问题是因为递归是从N开始 如果判断每一行有多少数字从而与K的值来进行比较？
因为每一行的数字数量规律为2的N-1次方
所以可以通过对1进行左移N-1位来得到上一行数字的数量

以下为源代码：

class Solution {
public:
    int kthGrammar(int N, int K) {
        if (N == 1) {
            return 0;
        }
        if (N == 2) {
            return K == 1? 0 : 1;
        }
        //因为每一行长度为2 的n-1次方  所以要计算上一行长度就得左移
        int len = (1 << (N-1)) / 2;
    
    if (K <= len) {
        return kthGrammar(N-1, K);
    } else {
        //取反  用另一种方法试试
        //位于后半段 K 的值肯定大于上一行的len值 所以是k - len
        return !kthGrammar(N-1, K-len);
    }
    }
};

938. 二叉搜索树的范围和

给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。

二叉搜索树保证具有唯一的值。

示例 1：

输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
输出：32

示例 2：

输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
输出：23

二叉搜索树就是左子树的值小于根节点，右子树的值大于根节点的二叉树
此题乍一看有些懵，一开始我以为是说要返回L和R之间的所有节点的值是按层返回的，不是按大小返回。
其实是返回所有大于等于L小于等于R的值所在节点。
因为二叉搜索树已经按规律为我们把数的大小排好序，那么我们只需要判断当前节点所在值如果小于L，那么就找该节点的下一个右子树上所在值（因为再循着左子树往下寻找，依然都是比L小的节点） 同理 当前节点所在值大于R 那么就找该节点的下一个左子树所在值。
如果当前节点值在L和R之间 那么就返回该节点值并继续递归该节点的左子树和右子树（如果他们存在的话）
源代码如下：

class Solution {
public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        if (root == NULL) {
            return 0;
        }
        if (root->val < L) {
            //那就要找大的
            return rangeSumBST(root->right, L, R);
        }
        if (root->val > R) {
            //太大，往小了找
            return rangeSumBST(root->left, L, R);
        }
        return root->val + rangeSumBST(root->left, L, R) + rangeSumBST(root->right, L, R);
    }
};