2/3/2018 contest 70

K-th Symbol in Grammar

it's bit operation, but I don't know the tricks right now.

public int kthGrammar(int N, int K) {
    return Integer.bitCount(K-1) & 1;
}

Split BST

Iterative method,

recursive method:

class Solution {
    public TreeNode[] splitBST(TreeNode root, int V) {
        return split(root, V);
    }

    TreeNode[] split(TreeNode root, int v)
    {
        if(root == null)return new TreeNode[]{null, null};

        if(root.val <= v){
            TreeNode[] res = split(root.right, v);
            root.right = res[0];
            res[0] = root;
            return res;
        }else{
            TreeNode[] res = split(root.left, v);
            root.left = res[1];
            res[1] = root;
            return res;
        }
    }
}