662. 二叉树最大宽度(优化解法，防止正常标记的id数超过int范围（全是右子树）)
List ls = new ArrayList<>(); // 记录每一层的最左节点初始id
public int widthOfBinaryTree(TreeNode root) {
return process(root,0,0);
}
//d表示第几层,id表示初始id
public int process(TreeNode root,int d,int id) {
if(root == null) {
return 0;
}
if(ls.size() == d) {
ls.add(id);
}
id = id - ls.get(d);
return Math.max(id + 1,Math.max(process(root.left,d + 1,id * 2),process(root.right,d + 1,id * 2 + 1)));
}
297.二叉树的序列化与反序列化
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
LinkedList ans = new LinkedList<>();
if(root == null) {
ans.add(null);
}else {
ans.add(String.valueOf(root.val));
Queue queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
TreeNode temp = queue.poll();
if(temp.left != null) {
ans.add(String.valueOf(temp.left.val));
queue.add(temp.left);
}else {
ans.add(null);
}
if(temp.right != null) {
ans.add(String.valueOf(temp.right.val));
queue.add(temp.right);
}else {
ans.add(null);
}
}
}
while(!ans.isEmpty() && ans.peekLast() == null) {
ans.pollLast();
}
StringBuilder sb = new StringBuilder();
sb.append("[");
String first = ans.pollFirst();
sb.append(first == null ? "null" : first);
while(!ans.isEmpty()) {
String temp = ans.pollFirst();
sb.append("," + (temp == null ? "null" : temp));
}
sb.append("]");
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String str[] = data.substring(1,data.length() - 1).split(",");
int index = 0;
TreeNode res = generateNode(str[index ++]);
Queue queue = new LinkedList<>();
if(res != null) {
queue.add(res);
}
while(!queue.isEmpty()) {
TreeNode temp = queue.poll();
temp.left = generateNode(index == str.length ? "null" : str[index ++]);
temp.right = generateNode(index == str.length ? "null" : str[index ++]);
if(temp.left != null) {
queue.add(temp.left);
}
if(temp.right != null) {
queue.add(temp.right);
}
}
return res;
}
public TreeNode generateNode(String s) {
if(s.equals("null")) {
return null;
}
return new TreeNode(Integer.valueOf(s));
}
300. 最长递增子序列(O(nlogn))
public int lengthOfLIS(int[] nums) {
List ls = new ArrayList<>();
ls.add(nums[0]);
for(int i = 1;i < nums.length;i ++) {
int x = f(ls,nums[i]);
if(x == -1) {
ls.set(0,Math.min(ls.get(0),nums[i]));
}else {
if(x + 1 == ls.size()) {
ls.add(nums[i]);
}else {
ls.set(x + 1,Math.min(ls.get(x + 1),nums[i]));
}
}
}
return ls.size();
}
//返回 < target最右
public int f(List ls,int target) {
int L = 0;
int R = ls.size() - 1;
int ans = -1;
int M = 0;
while(L <= R) {
M = (L + R) >> 1;
if(ls.get(M) >= target) {
R = M - 1;
}else {
ans = M;
L = M + 1;
}
}
return ans;
}