今天周一，刷题继续。
合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
思路：首先我记得以前做过类似的题，如果能不借助于list就要自排序，反正我首先用最笨但是每个人都会的方法把第一版本做出来了，当然性能低是意料之中的。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<m;i++){
list.add(nums1[i]);
}
for(int i:nums2){
list.add(i);
}
Collections.sort(list);
for(int i=0;i<m+n;i++){
nums1[i]=list.get(i);
}
}
}
第一版本做完了才开始有心情做第二个版本，从优化开始讲起，我接着开始分析题目，发现可以直接把nums2插入到nums1中，然后在Array.sort(),美滋滋，运行速度也快，然后出题的意义没了。还是老老实实自己写吧：
public void merge(int[] nums1, int m, int[] nums2, int n) {
int [] arr = new int[m];
for(int i=0;i<arr.length;i++){
arr[i]=nums1[i];
}
int k = 0;
int i = 0;
int j = 0;
while(i<m && j<n){
if(arr[i]<nums2[j]){
nums1[k]=arr[i];
i++;
}else{
nums1[k]=nums2[j];
j++;
}
k++;
}
if(i<m){//说明数组1还有元素
for(;i<m;i++){
nums1[k]=arr[i];
k++;
}
}else if(j<n){
for(;j<n;j++){
nums1[k]=nums2[j];
k++;
}
}
}
如图所示吧，其实这个返回值如果是自己定义的更简单了，但是因为返回的就是nums1，所以没办法，只能做一个nums1的副本arr，然后从头开始判断，双指针法，把arr和nums2按顺序插入nums1.得出的答案就是想要的。
本来我还以为这么麻烦会性能不太好呢，结果居然是0ms。
接着看了大神解析，很多用了递归啥的，不过因为我的方法可以了，所以也没仔细研究。其实想了很多思路。比如这个nums2插入到nums1.可不可以理解为把nums2的每一个元素，插入到有序数组nums1？这样循环下来也能满足需求，但是性能怎么样因为我没测试所以也不知道。然后今天因为工作原因，本来计划好的三道题都没做完，所以先不多想了，继续往下做。
相同的树
给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
(因为这个题的题目不好复制粘贴，所以直接截图)
思路：比较树、链表啥的，递归没跑了，所以重点就是怎么递归咯、因为树分左右两叉。所以结果也应该是两边都相等才能。这个因为做过类似的功能，所以直接上代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
//俩都是空则true
if(p==null && q==null){
return true;
}
//如果都不为空并且val相等才判断左节点右节点
if(p!=null && q!=null && p.val==q.val){
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}else{
//走到这说明一个空一个不是空，或者值不相等，直接返回false；
return false;
}
}
}
这道题比较简单，所以不多说了，而且因为我做过类似的，所以思路也很清晰。继续下一题、
对称二叉树
题目：给定一个二叉树，检查它是否是镜像对称的。（题目不好复制粘贴，所以截图）
思路：这个题我觉得跟上道题一起做简直是送分的，所谓的中间对称，不就是从中劈开，节点左子节点等于节点右子节点。反之亦然。上一个是相等，这一个是相反不就ok了，递归的方法很容易做出来：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
//我理解的对称的概念：从中劈开，左右一样
if(root==null || (root.left==null && root.right==null)){
return true;
}
if(root.left!=null && root.right!=null && root.left.val==root.right.val){
return isSymmetric(root.left,root.right);
}else{
return false;
}
}
public boolean isSymmetric(TreeNode p,TreeNode q) {
if(p==null && q==null){
return true;
}
if(p!=null && q!=null && p.val==q.val){
return isSymmetric(p.left,q.right) && isSymmetric(p.right,q.left);
}else{
return false;
}
}
}
这个前期判断有点麻烦，就是首先这个节点不是空节点，不然肯定是对称的，其次如果只有一个根节点肯定是对称的。
其次如果只有两个节点，那么这个一定要相等。这些都满足了才需要往下判断。
判断的方法就是上面的判断两个树是不是相等反过来而已，没什么可多数的。但是题目要求最好是递归和迭代两种方法，所以接下来继续看迭代的方法：
算了，迭代不出来了，直接看大神解析吧，虽然我不会，但是我已经预测到迭代应该就几行代码，然后看了豁然开朗。
好的，看了题解，然后发现了一句非常好的话：
一看就会，一写就废。
哈哈，继续说迭代法怎么比较对称吧。
这个题解里用了一种我不是很了解的数据结构，队列Queue。说实话这个数据格式我几乎没用过。然后这里如果是对称的树，从根节点不算，起码第二层的节点应该是相等的，然后对应的节点值一样，节点的子节点互相反转，也就是left=right。
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
q.add(root);
while (!q.isEmpty()) {
TreeNode t1 = q.poll();
TreeNode t2 = q.poll();
if (t1 == null && t2 == null) continue;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
q.add(t1.left);
q.add(t2.right);
q.add(t1.right);
q.add(t2.left);
}
return true;
}
这个题说真的，我到现在还有点懵，只能说百分之八十理解百分之二十脑补。只能靠猜的。所以也就不多说了，今天就到这里了。
如果稍微帮到你了记得点个喜欢点个关注呦！也祝大家工作顺顺利利！
