442、数组中重复的数据
给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围[1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法（空间复杂度为O(1)）解决此问题
需要注意的是，遍历数组nums的过程中，遍历到的元素num可能已经被改成负数，因此在计算下标index时需要对num取绝对值然后减1
class Solution {
public List findDuplicates(int[] nums) {
List duplicates = new ArrayList();
int n = nums.length;
for (int i = 0; i < n; i++) {
int num = nums[i];
int index = Math.abs(num) - 1;
if (nums[index] > 0) {
nums[index] = -nums[index];
} else {
duplicates.add(index + 1);
}
}
return duplicates;
}
}
942、增减字符串匹配
由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:
- 如果 perm[i] < perm[i + 1] ，那么 s[i] == 'I'
- 如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D'
给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。
直觉：遇到I,就给他填入最小值 遇到D就给他最大值 s.length==4 那么最小值是1,最大值是4
class Solution {
public int[] diStringMatch(String s) {
//直觉：遇到I,就给他填入最小值 遇到D就给他最大值 s.length==4 那么最小值是1,最大值是4
int []res=new int[s.length()+1];
int left=0,right=s.length();
int index=0;
for(int i=0;i
606、根据二叉树创建字符串
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
题目的意思如下：
二叉树[root,left,right]，则转换为root(left)(right)。如果只有left为空节点，则输出root()(right)；如果只有right为空节点则可以忽略右节点的()，输出为root(left)
class Solution {
public String tree2str(TreeNode root) {
StringBuilder sb = new StringBuilder();
//二叉树[root,left,right]，则转换为root(left)(right)。
sb.append(root.val);
//如果只有left为空节点(left为空而right不为空),则输出root()(right)
//如果left不为空，就照样遍历
if (root.left != null) {
sb.append("(");
sb.append(tree2str(root.left));
sb.append(")");
} else if (root.right != null) {
sb.append("()");
}
//如果只有right为空节点则可以忽略右节点的()，输出为root(left)，如果right不为空,那么照样遍历
if (root.right != null) {
sb.append("(");
sb.append(tree2str(root.right));
sb.append(")");
}
return sb.toString();
}
}
617、合并二叉树
给你两棵二叉树： root1 和 root2 。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。返回合并后的二叉树。注意: 合并过程必须从两个树的根节点开始。
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1==null&&root2==null) return null;
if(root1==null) return root2;
if(root2==null) return root1;
TreeNode root=new TreeNode(root1.val+root2.val);
root.val=root1.val+root2.val;
root.left=mergeTrees(root1.left,root2.left);
root.right=mergeTrees(root1.right,root2.right);
return root;
}
}
700、二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
根据二叉搜索树的性质：比根结点小的数都放在左子树，比根结点大的数都放在右子树
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
return BSTOrder(root,val);
}
public TreeNode BSTOrder(TreeNode root, int val){
if(root==null) return null;
if(root.val==val) return root;//只要找到这个结点,那么return root 他就会把他后面的所有结点也一起输出,类似链表
if(root.valval) return searchBST(root.left,val);
return null;
}
}
