今天周一，刷題繼續(xù)。

合并兩個有序數(shù)組

給定兩個有序整數(shù)數(shù)組 nums1 和 nums2，將 nums2 合并到 nums1 中，使得 num1 成為一個有序數(shù)組。

說明:
初始化 nums1 和 nums2 的元素數(shù)量分別為 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);
        }
    }
}

第一版本做完了才開始有心情做第二個版本，從優(yōu)化開始講起，我接著開始分析題目，發(fā)現(xiàn)可以直接把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){//說明數(shù)組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的每一個元素，插入到有序數(shù)組nums1？這樣循環(huán)下來也能滿足需求，但是性能怎么樣因為我沒測試所以也不知道。然后今天因為工作原因，本來計劃好的三道題都沒做完，所以先不多想了，繼續(xù)往下做。

相同的樹

給定兩個二叉樹，編寫一個函數(shù)來檢驗它們是否相同。如果兩個樹在結構上相同，并且節(jié)點具有相同的值，則認為它們是相同的。

(因為這個題的題目不好復制粘貼，所以直接截圖)

image.png

思路：比較樹、鏈表啥的，遞歸沒跑了，所以重點就是怎么遞歸咯、因為樹分左右兩叉。所以結果也應該是兩邊都相等才能。這個因為做過類似的功能，所以直接上代碼

/**
 * 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相等才判斷左節(jié)點右節(jié)點
        if(p!=null && q!=null && p.val==q.val){
             return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }else{
            //走到這說明一個空一個不是空，或者值不相等，直接返回false；
            return false;
        }     
    }
}

這道題比較簡單，所以不多說了，而且因為我做過類似的，所以思路也很清晰。繼續(xù)下一題、

對稱二叉樹

題目：給定一個二叉樹，檢查它是否是鏡像對稱的。（題目不好復制粘貼，所以截圖）

image.png

/**
 * 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;
        }
    }
}

這個前期判斷有點麻煩，就是首先這個節(jié)點不是空節(jié)點，不然肯定是對稱的，其次如果只有一個根節(jié)點肯定是對稱的。
其次如果只有兩個節(jié)點，那么這個一定要相等。這些都滿足了才需要往下判斷。
判斷的方法就是上面的判斷兩個樹是不是相等反過來而已，沒什么可多數(shù)的。但是題目要求最好是遞歸和迭代兩種方法，所以接下來繼續(xù)看迭代的方法：
算了，迭代不出來了，直接看大神解析吧，雖然我不會，但是我已經(jīng)預測到迭代應該就幾行代碼，然后看了豁然開朗。
好的，看了題解，然后發(fā)現(xiàn)了一句非常好的話：
一看就會，一寫就廢。
哈哈，繼續(xù)說迭代法怎么比較對稱吧。
這個題解里用了一種我不是很了解的數(shù)據(jù)結構，隊列Queue。說實話這個數(shù)據(jù)格式我?guī)缀鯖]用過。然后這里如果是對稱的樹，從根節(jié)點不算，起碼第二層的節(jié)點應該是相等的，然后對應的節(jié)點值一樣，節(jié)點的子節(jié)點互相反轉(zhuǎn)，也就是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;
}

這個題說真的，我到現(xiàn)在還有點懵，只能說百分之八十理解百分之二十腦補。只能靠猜的。所以也就不多說了，今天就到這里了。
如果稍微幫到你了記得點個喜歡點個關注呦！也祝大家工作順順利利！