知識點總結

set判斷元素是否存在 set.contains();
回傳空陣列 return null return new int[0]; return new int[]{};
回傳新創建的非空陣列 return new int[]{i,map.get(target-nums[i])};

陣列元素放入map

getOrDefault：當Map集合中有這個key時，就使用這個key對應的value值，如果沒有這個key就使用默認值defaultValue

for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }

取堆疊頂元素，也是需要判定堆疊是否為空的，否則會爆出空堆疊例外
判斷堆疊是否為空：stack.isEmpty();

if(!stack.isEmpty()&&stack.peek()=='[') stack.pop();

總結：注意實體化佇列不能用 Queuequeue=new Queue();
也不能用Queuequeue=new Deque();因為Queue()和Deque()都是抽象類，不能實體化，而是用的Queuequeue=new LinkedList();

佇列添加和移除元素 add remove

用遞回做二叉樹的題的時候，可以先想想如果只有一顆二叉樹，一個根節點和它的左右節點，你會怎么處理

2021.07.28（第1天）陣列

1 217 存在重復的元素

class Solution {
    public boolean containsDuplicate(int[] nums) {
       Set<Integer>set=new HashSet();
       for(int i=0;i<nums.length;i++)
       {
           if(set.contains(nums[i])) 
           {
              return true;
           }
           set.add(nums[i]);
       }
       return false;
    }
}

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
}


作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/contains-duplicate/solution/cun-zai-zhong-fu-yuan-su-by-leetcode-sol-iedd/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

2 53. 最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
          int dp[]=new int [nums.length];
          dp[0]=nums[0];
          int max=dp[0];
          for(int i=1;i<nums.length;i++)
          {
              dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);
              max=Math.max( dp[i],max);
          }
       return max;
    }
}

2021.07.29 (第2天)陣列

3 1. 兩數之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
      Map<Integer,Integer>map=new HashMap();
      for(int i=0;i<nums.length;i++)
      {
          if(map.containsKey(target-nums[i]))
          {
                return new int[]{i,map.get(target-nums[i])};
          }     
         map.put(nums[i],i);
      }
      return new int[]{};
    }
}

4 88. 合并兩個有序陣列

最開始想的是從前往后插入，一次比較，但是num1前面的元素不好處理啊
還有一個方法就是重新創建一個大小為m+n的陣列，但是這樣太low了，看了帖子發現可以從后往前插入，，，，，

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1=m-1;int p2=n-1;
        int curr=m+n-1;
        while(p2>=0&&p1>=0)
        {       
        if(nums1[p1]>=nums2[p2])//p1指向的數大于等于p2執行的數
        {
            nums1[curr--]=nums1[p1];
            p1--;
        }
        else
        {
           nums1[curr--]=nums2[p2]; 
           p2--;
        }   
       }   
       //看看是誰先走完了
       if(p1<0)
       {
           while(p2>=0)
           {
               nums1[curr--]=nums2[p2]; 
               p2--;
           }
       }
       else{
            while(p1>=0)
           {
               nums1[curr--]=nums1[p1]; 
               p1--;
           }

       }
    }
}

直接合并后排序？？？？？

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }
}


作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

這個比我的簡潔

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;
        int cur;
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {
                cur = nums2[p2--];
            } else if (p2 == -1) {
                cur = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
    }
}

作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

2021.07.30(第3天) 陣列

5 121. 買賣股票的最佳時機

思路：找到當前天數之前的最小值，用今天的價格減去之前的最小值（就是假設在最小值處買入），這樣，直到遍歷到最后一天，求得利潤最大值

class Solution {
    public int maxProfit(int[] prices) {
       int min=prices[0];
       int max=0;
       for(int i=1;i<prices.length;i++)
       {
           min=Math.min(min,prices[i]);
           max=Math.max(prices[i]-min,max);
       }
       return max;
    }   
}

6 350. 兩個陣列的交集 II

思路：把一個陣列的元素全部存進map,map的key為數字，value為該數字出現的次數，重復出現的數字就次數++

然后用陣列2來匹配map的key，如果匹配，就把這個匹配的值加入 list，同時，這個map中被匹配的數的次數減1，下次再匹配到，但是map中對應的value為0的話，就不加入list了，

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
       Map<Integer,Integer>map=new HashMap();
       List<Integer>list=new ArrayList();
       for(int i=0;i<nums1.length;i++)
       {
           if(map.containsKey(nums1[i]))
           {
               map.put(nums1[i],map.get(nums1[i])+1);
           }
           else
           {
               map.put(nums1[i],1);
           }
       }
       for(int i=0;i<nums2.length;i++)
       {
              if(map.containsKey(nums2[i])&&map.get(nums2[i])!=0)
              {
                  list.add(nums2[i]);
                  map.put(nums2[i],map.get(nums2[i])-1);//相當于取出來一個，把map中元素對應的個數減一
              }
       }
      int[] arr = new int [list.size()];      
    //  list.toArray(arr);
    for(int j=0;j<list.size();j++) arr[j]=list.get(j);
       return arr;
    }
}

官方還是官方啊，思路差不多，但是代碼簡潔

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}


作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution/liang-ge-shu-zu-de-jiao-ji-ii-by-leetcode-solution/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

思路2：排序+雙指標
如果兩個陣列是有序的，則可以使用雙指標的方法得到兩個陣列的交集，

首先對兩個陣列進行排序，然后使用兩個指標遍歷兩個陣列，

初始時，兩個指標分別指向兩個陣列的頭部，每次比較兩個指標指向的兩個陣列中的數字，如果兩個數字不相等，則將指向較小數字的指標右移一位，如果兩個數字相等，將該數字添加到答案，并將兩個指標都右移一位，當至少有一個指標超出陣列范圍時，遍歷結束，

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}


作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution/liang-ge-shu-zu-de-jiao-ji-ii-by-leetcode-solution/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

2021.07.31(第4天) 陣列

7 566. 重塑矩陣

思路：直接把原矩陣拉成一維的list，再依次放入新矩陣

class Solution {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int m=mat.length; int n=mat[0].length;
        if(m*n!=r*c) return mat;//沒有辦法轉化,輸出原矩陣
        int convert[][]=new int[r][c];
        List<Integer>list=new ArrayList();
         for(int i=0;i<m;i++)
          {
              for(int j=0;j<n;j++)
              {
                  list.add(mat[i][j]);
              }
          }
         int count=0;
          for(int i=0;i<r;i++)
          {
              for(int j=0;j<c;j++)
              {
                  convert[i][j]=list.get(count++);
              }
          }
    return convert;
    }
}

思路2：映射

class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        int m = nums.length;
        int n = nums[0].length;
        if (m * n != r * c) {
            return nums;
        }

        int[][] ans = new int[r][c];
        for (int x = 0; x < m * n; ++x) {
            ans[x / c][x % c] = nums[x / n][x % n];
        }
        return ans;
    }
}

8 118. 楊輝三角

思路，找規律，變聲是1，中間的元素的值為list.get(i-1).get(j-1)+list.get(i-1).get(j)

class Solution {
    public List<List<Integer>> generate(int numRows) {
           List<List<Integer>> list=new ArrayList();    
           for(int i=0;i<numRows;i++)
           {
                list.add(new ArrayList());//這里不add的話，下邊get就會報錯哦
               for(int j=0;j<=i;j++)
               {
                   if(j==0||j==i) list.get(i).add(1);
                   else list.get(i).add(list.get(i-1).get(j-1)+list.get(i-1).get(j));
               }
           }                                   
         return list;
    }
}

2021.08.01(第5天) 陣列

9 36. 有效的數獨

10 73. 矩陣置零

解題思路：兩個標記陣列分別記錄每一行和每一列是否有零出現，

具體地，我們首先遍歷該陣列一次，如果某個元素為 000，那么就將該元素所在的行和列所對應標記陣列的位置置為 true\text{true}true，最后我們再次遍歷該陣列，用標記陣列更新原陣列即可

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = col[j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

常量空間的思路，就是用原來陣列的第一行和第一列代替我們用來標記的陣列空間，
先用兩個常量標記第一行和第一列是否有0，
然后遍歷陣列除了第一行和第一列的部分，如果出現0，就把對應的i,j映射到第一行和第一列去置零
然后再遍歷一次除了第一行和第一列的部分把第一行和第一列置為0的對應的i,j的地方都置為0
然后判斷原來的標志位，加入原來第一行有0，像現在就把第一行全部置0，加入原來第一行沒有0，就不用改了，應為應該改成0的地方現在已經是0了

class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        boolean row0_flag = false;
        boolean col0_flag = false;
        // 第一行是否有零
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0) {
                row0_flag = true;
                break;
            }
        }
        // 第一列是否有零
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                col0_flag = true;
                break;
            }
        }
        // 把第一行第一列作為標志位
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        // 置0
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (row0_flag) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col0_flag) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        } 
    }
}

2021.08.02（第6天） 字串

11 387. 字串中的第一個唯一字符

思路一：遍歷字串，存盤每一個字符出現的次數，之后再遍歷一次字串，找到第一個頻次為1的數

思路二：Map存盤字符和索引，如果多次出現，就把索引設定為1，最后遍歷哈希表，找到索引是1的字符

思路3 ：用佇列

class Solution {
    public int firstUniqChar(String s) {
        Map<Character,Integer>map=new HashMap();
        for(int i=0;i<s.length();i++)
        {
            if(map.containsKey(s.charAt(i)))
                map.put(s.charAt(i),map.get(s.charAt(i))+1);
            else
                map.put(s.charAt(i),1);
        }
       
       for(int i=0;i<s.length();i++)
       {
           if(map.get(s.charAt(i))==1)
             return i;
       }
       return -1;
    }
}

用陣列會快很多

class Solution {
   public int firstUniqChar(String s) {
       int[] arr = new int[26];
        int n = s.length();
        for (int i = 0; i < n; i++) {
            arr[s.charAt(i)-'a']++ ;
        }
        for (int i = 0; i < n; i++) {
            if (arr[s.charAt(i)-'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
}

12 383. 贖金信

思路：用兩個Map分別統計兩個字串總每個字符出現的頻次
然后遍歷第一個字串，比較它在兩個字串中出現頻次的大小關系
需要注意的是，map的get方法，如果key不存在的話，會報空指標例外，所以需要先用containsKey判斷是否存在，存在再使用get方法取出value

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
         Map<Character,Integer>map1=new HashMap();
         Map<Character,Integer>map2=new HashMap();
        for(int i=0;i<ransomNote.length();i++) 
        {
          char ch=ransomNote.charAt(i);
          map1.put(ch,map1.getOrDefault(ch,0)+1);
        }
        for(int i=0;i<magazine.length();i++) 
        {
          char ch=magazine.charAt(i);
          map2.put(ch,map2.getOrDefault(ch,0)+1);
        }
        for(int i=0;i<ransomNote.length();i++) {
           char ch=ransomNote.charAt(i);
           if(!map2.containsKey(ch)) 
                return false;
           if(map1.get(ch)>map2.get(ch))
             return false;
        }
         return true;     
    }
}

這個用陣列的思路就快很多

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        //記錄雜志字串出現的次數
        int[] arr = new int[26];
        int temp;
        for (int i = 0; i < magazine.length(); i++) {
            temp = magazine.charAt(i) - 'a';
            arr[temp]++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            temp = ransomNote.charAt(i) - 'a';
            //對于金信中的每一個字符都在陣列中查找
            //找到相應位減一，否則找不到回傳false
            if (arr[temp] > 0) {
                arr[temp]--;
            } else {
                return false;
            }
        }
        return true;
    }
}

13 242. 有效的字母異位詞

解題思路：用一個陣列存放26個小寫字母的出現次數，對于第一個字串，對每一個出現的字母做次數加法

對于第二個字串，對每一個出現的字母做次數減法

最后，如果他們是字母異位詞，那么，陣列的每一個數都應該是0

class Solution {
    public boolean isAnagram(String s, String t) {                      
         int arr[]=new int[26];
         for(int i=0;i<s.length();i++)
         {
             char ch=s.charAt(i);
             int num=ch-'a';
             arr[num]++;
         }
         for(int i=0;i<t.length();i++)
         {
             char ch=t.charAt(i);
             int num=ch-'a'; 
             arr[num]--;             
         }
         for(int i=0;i<26;i++)
         {
             if(arr[i]!=0) return false;
         }
         return true;       
    }
}

思路2：排序之后比較，確實把我秀到了

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }
}

2021.08.03 (第7天) 鏈表

14 141. 環形鏈表

思路：定義快慢指標，同時從頭結點出發，快指標比慢指標每次快一步，慢指標每次走一步，開指標每次走2步，

如果鏈表沒有環，則快指標走到終點，程式結束
如果鏈表有環，則慢指標會追上快指標

思考，快指標為什么走2步，而不是其他步數？
參考：為什么快指標速度一般為慢指標的兩倍？

如果你是高倍的話，那么快指標將會飛快地到達第一個環，而慢指標則會很慢才能到達第一個環，中間這段程序中快指標在第一個環內將會無意義高速移動，

請問在查找單鏈表環時那個快的指標的步長為什么是2?3倍4倍？

為什么用快慢指標找鏈表的環，快指標和慢指標一定會相遇？
詳解為什么用一步兩步快慢指標？三步四步可以嗎

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)
               return true;            
        }
        return false;
    }
}

思路2：使用hash表存盤訪問過的結點，如果結點被重復訪問，說明有環

public class Solution {
    public boolean hasCycle(ListNode head) {
       Set<ListNode>set=new HashSet();
       while(head!=null){
          if(!set.add(head))
             return true;
          head=head.next;
       }
       return false;
    }
}

擴展

求環形鏈表的入環點

142. 環形鏈表 II

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast){
                fast=head;
                while(slow!=fast){//找到相遇結點之后，讓fast指向頭結點，然后fast和slow同時移動，相遇的結點即為環的入口
                    slow=slow.next;
                    fast=fast.next;
                }
                return fast;
            }
        }
        return null;
    }
}

思路2：用hash表，遍歷結點，hash表中第一個重復的結點即為入環點

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode>set=new HashSet();
        while(head!=null)
        {
            if(!set.add(head))
               return head;
            head=head.next;
        }
        return null;
    }
}

求環的長度？

求有環單鏈表中的環長、環起點、鏈表長

從相遇點開始，假設慢指標有走了半圈，那么快指標走了一圈又回到最開始的相遇點

如果慢指標再走半圈，慢指標回到了最開始的相遇點，而快指標則又走了一圈回到相遇點

此時兩指標再次相遇

所以從相遇點開始，兩指標再次相遇時，慢指標走過的距離即為環的長度

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast){
                int length=1;
                fast=fast.next.next;
                slow=slow.next;
                while(slow!=fast){//找到相遇結點之后，讓fast指向頭結點，然后fast和slow同時移動，相遇的結點即為環的入口
                     length++;
                    slow=slow.next;
                    fast=fast.next.next;
                }
                System.out.println(length);
              //  return fast;
            }
        }
        return null;
    }
}

///獲取鏈表環長
 55 int getRingLength(LinkNode *ringMeetNode){
 56     int RingLength=0;
 57     LinkNode *fast = ringMeetNode;
 58     LinkNode *slow = ringMeetNode;
 59     for(;;){
 60         fast = fast->next->next;
 61         slow = slow->next;
 62         RingLength++;
 63         if(fast == slow)
 64             break;
 65     }
 66     return RingLength;
 67 }

15 21. 合并兩個有序鏈表

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
         if(l1==null) return l2;
         if(l2==null) return l1;
         ListNode head1=l1;
         ListNode head2=l2;
         ListNode head;
         head=l1.val<=l2.val?l1:l2;
         if(head==l1) l1=l1.next;
         else l2=l2.next;
         ListNode temp=head;
         while(l1!=null||l2!=null){
            if(l1==null) {
              temp.next=l2;
              break;
            }
            if(l2==null){
               temp.next=l1;
               break;
            } 
            if(l1.val<=l2.val)
            {
                temp.next=l1;
                l1=l1.next;
            }
            else
            {
                temp.next=l2;
                l2=l2.next;
            }
            temp=temp.next;
         }
         return head;
    }
}

官方簡潔到我要崩潰

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一個還未被合并完，我們直接將鏈表末尾指向未合并完的鏈表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

這個遞回我服氣

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }
}


作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

16 203. 移除鏈表元素

class Solution {
    public ListNode removeElements(ListNode head, int val) {
         ListNode head2=new ListNode(-1);    
         ListNode temp=head2;
         while(head!=null){         
            if(head.val!=val) {
                temp.next=head;
                temp=temp.next;             
            }
            else{
               temp.next=null;//為了避免最后一個結點無法處理，因為我們上面是遇到val相同的直接跳過
         //但是對于[1,2,6,3,4,5,6]這種例子，6還是會接在5的后面，[1,2,6,3,4,5,6，6,6,6]這種后面的6都沒辦法處理
            }          
            head=head.next;
         }        
         return head2.next;
    }
}

當我把while回圈去掉，按理說只是添加了1這個結點到temp后面，但是我們不要忘記了，1的后面也是有結點的

當我把else去掉，為什么只回傳了1？

這是因為不加else的話，每一次temp這個參考把當前head指標指向的結點的下一個結點給置空了，，，，

思路2 遞回

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }
}


作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/remove-linked-list-elements/solution/yi-chu-lian-biao-yuan-su-by-leetcode-sol-654m/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        dfs(dummy, dummy.next, val);
        return dummy.next;
    }
    void dfs(ListNode prev, ListNode root, int val) {
        if (root == null) return ;
        if (root.val == val) {
            prev.next = root.next;
        } else {
            prev = root;
        }
        dfs(prev, prev.next, val);
    }
}


作者：AC_OIer
鏈接：https://leetcode-cn.com/problems/remove-linked-list-elements/solution/gong-shui-san-xie-yi-chu-lian-biao-yuan-ca6fu/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

迭代思路2

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null) {
            if (temp.next.val == val) {
                temp.next = temp.next.next;
            } else {
                temp = temp.next;
            }
        }
        return dummyHead.next;
    }
}


作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/remove-linked-list-elements/solution/yi-chu-lian-biao-yuan-su-by-leetcode-sol-654m/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

2021.08.04(第8天) 鏈表

17 83. 洗掉排序鏈表中的重復元素

遍歷鏈表，如果該節點的val值與新鏈表的尾節點的val值不相等，就把它加入到新的鏈表中

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
           ListNode temp=new ListNode(101);
           ListNode temp2=temp;
          while(head!=null){
              if(head.val!=temp2.val){
                  temp2.next=head;
                  temp2=temp2.next;
              }
               else{
                 temp2.next=null; 
               }
              head=head.next;
          }   
         return temp.next;
    }
}

18 206. 反轉鏈表

思路1：非原地反轉，利用了o(n)的額外空間

class Solution {
    public ListNode reverseList(ListNode head) {
     ListNode temp=new ListNode(0);
    // ListNode temp2=temp;
     ListNode head2=head;
     while(head!=null){
         ListNode next=temp.next;//暫存新鏈表的第二個節點
         temp.next=new ListNode(head.val);
         temp.next.next=next;
         head=head.next;      
     }
     return temp.next;
    }
}

遞回思路：
提示，把長鏈表切分成頭結點和子鏈表醬紫遞回
當只有一個節點的時候，直接回傳，
當有兩個節點的時候
head.next.next=head;
head.next=null;

推薦 leetcode206/劍指 Offer 24. 反轉鏈表

2021.08.05(第9天) 堆疊 / 佇列

19 20. 有效的括號

總結：取堆疊頂元素，也是需要判定堆疊是否為空的，否則會爆出空堆疊例外
判斷堆疊是否為空：stack.isEmpty();

if(!stack.isEmpty()&&stack.peek()=='[') stack.pop();

class Solution {
    public boolean isValid(String s) {
         Stack<Character>stack=new Stack();
         for(int i=0;i<s.length();i++){
             if(s.charAt(i)==')'){
                 if(!stack.isEmpty()&&stack.peek()=='(') stack.pop();
                 else stack.push(s.charAt(i));
             }
             else if(s.charAt(i)=='}'){
                 if(!stack.isEmpty()&&stack.peek()=='{') stack.pop();
                 else stack.push(s.charAt(i));
             }
             else if(s.charAt(i)==']'){
                 if(!stack.isEmpty()&&stack.peek()=='[') stack.pop();
                 else stack.push(s.charAt(i));
             }
             else
               stack.push(s.charAt(i));
         }        
       return stack.isEmpty();    
    }
}

修改了一下，遇到不匹配直接回傳false

class Solution {
    public boolean isValid(String s) {
         Stack<Character>stack=new Stack();
         for(int i=0;i<s.length();i++){
             if(s.charAt(i)==')'){
                 if(!stack.isEmpty()&&stack.peek()=='(') stack.pop();
                 else return false;
             }
             else if(s.charAt(i)=='}'){
                 if(!stack.isEmpty()&&stack.peek()=='{') stack.pop();
                 else  return false;
             }
             else if(s.charAt(i)==']'){
                 if(!stack.isEmpty()&&stack.peek()=='[') stack.pop();
                 else  return false;
             }
             else
               stack.push(s.charAt(i));
         }        
       return stack.isEmpty();    
    }
}

20 232. 用堆疊實作佇列

解題思路，用兩個輔助堆疊實作佇列的先入先出功能
假設現在有1 2 3 4 5
我們把他們都壓入stack,彈出順序就是5 4 3 2 1 ，彈出的時候我們把彈出的元素壓入stack2
那么stack2的入堆疊殊順序是5 4 3 2 1 ，彈出順序就是1 2 3 4 5 實作了佇列的功能
即封裝成一個佇列的話，壓入元素時，壓入stack,彈出元素時，先從stack彈出到stack2,在從stack2再從stack2彈出元素

但是實際情況要求可以隨時壓入元素和彈出元素

第一步：實作壓入元素，直接壓入stack
第二步：彈出元素，當stack2不為空的時候，直接彈出stack2的堆疊頂元素，當stack2為空，就把stack里面的元素彈出到stack2，在彈出堆疊頂元素
第三步：實作peek，就是跟第二步思路差不多，只不過不用彈出堆疊頂元素，而是回傳堆疊頂元素
第四步：判空,當兩個堆疊都為空的時候，說明佇列為空

class MyQueue {

    /** Initialize your data structure here. */
   Stack<Integer>stack=new Stack();
   Stack<Integer>stack2=new Stack();

   
    public MyQueue() {
       
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stack.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(!stack2.isEmpty())     
            return stack2.pop();       
        else{
            while(!stack.isEmpty())
              stack2.push(stack.pop());   
            return stack2.pop();                     
        }
    }
    
    /** Get the front element. */
    public int peek() {
       if(!stack2.isEmpty())     
            return stack2.peek();       
        else{
            while(!stack.isEmpty())
              stack2.push(stack.pop());   
            return stack2.peek();                     
        }
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        if(stack.isEmpty()&&stack2.isEmpty())  
            return true;
        return false;
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

注意代碼可以簡化
比如peek()里面兩個return 陳述句是一樣的，可以改一下，比如判空，直接 return inStack.isEmpty() && outStack.isEmpty();它不香嗎

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public MyQueue() {
        inStack = new LinkedList<Integer>();
        outStack = new LinkedList<Integer>();
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.pop();
    }
    
    public int peek() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}


作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/implement-queue-using-stacks/solution/yong-zhan-shi-xian-dui-lie-by-leetcode-s-xnb6/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

我們也可以用一個變數記住stack的堆疊底元素，這樣在訪問peek的時候如果stack2為空，就可以直接回傳front

public void push(int x) {
    if (s1.empty())
        front = x;
    s1.push(x);
}

用堆疊實作佇列

2021.08.06(第10天) 樹

21 144. 二叉樹的前序遍歷

思路一：遞回
前序遍歷就是先遍歷中間節點，然后遍歷左節點，右節點
我們找到第一個根節點，然后又會找到他的左節點，把這個左節點作為根節點，繼續遍歷，左子樹遍歷完之后，遍歷右子樹

class Solution {
    List<Integer>list=new ArrayList();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null) 
            return  list;
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);  
        return list; 
    }   
}

思路二：迭代
把根節點入堆疊，然后堆疊非空為回圈條件，每次彈出堆疊頂元素，壓入該元素的右節點和左節點

class Solution {  
    public List<Integer> preorderTraversal(TreeNode root) {   
       Stack<TreeNode>stack=new Stack(); 
       List<Integer> list =new ArrayList();
      if(root==null) 
         return list;      
       stack.push(root);     
       while(!stack.isEmpty()){
       TreeNode temp=stack.pop();
        list.add(temp.val);
        if(temp.right!=null)
          stack.push(temp.right);
         if(temp.left!=null)
          stack.push(temp.left);
      } 
         return list;  
    }
}

其他：參考
leetcode 144. 二叉樹的前序遍歷

22 94. 二叉樹的中序遍歷

思路一：遞回，先一直遍歷到最下面的左節點，將該節點加入list，然后將該節點的父節點加入list,然后是

class Solution {    
    public List<Integer> inorderTraversal(TreeNode root) {
        List <Integer>list=new ArrayList();
        dfs( root,list);
        return list;
    }
    public void dfs(TreeNode root,List <Integer>list)
    {
         if(root==null) return ;
         dfs(root.left,list);
         list.add(root.val);
         dfs(root.right,list);
         return ;
    }
}

思路二：迭代
先把根節點以及所有左節點壓入堆疊，然后從最后一個左節點開始，如果有右節點，先把右節點及右節點的所有左節點壓入堆疊，之后依次取出

class Solution {    
    public List<Integer> inorderTraversal(TreeNode root) {
        List <Integer>list=new ArrayList();
        Stack<TreeNode>stack=new Stack();   
        if(root==null) 
           return list;              
         TreeNode temp=root;
            while(temp!=null){
            stack.push(temp);
            temp=temp.left;
        }
        while(!stack.isEmpty()){          
           TreeNode temp1=stack.pop();           
           list.add(temp1.val);
           if(temp1.right!=null){
               TreeNode temp2=temp1.right;             
                 while(temp2!=null){
                     stack.push(temp2);
                     temp2=temp2.left;
            }
           }
        }  
      return list;
    }
}

官方的迭代，很簡潔

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stk = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

23 145. 二叉樹的后序遍歷

思路一：遞回

每個節點只有把它的左節點和右節點遍歷完之后才把它自己加入list

class Solution {
   List<Integer>list=new ArrayList();
    public List<Integer> postorderTraversal(TreeNode root) {
      if(root==null) return list;
      dfs(root);
      return list;
    }
    public void dfs(TreeNode root){
        if(root==null) return;
        dfs(root.left);
        dfs(root.right);
        list.add(root.val);
    }
}

思路2 :迭代1
用雙向鏈表，往前加元素，正好跟前序遍歷相反

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> ans = new LinkedList<>();
        if (null == root) return ans;
        stack.addFirst(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.removeFirst();
            ans.addFirst(node.val);
            if (null != node.left) {
                stack.addFirst(node.left);
            }
            if (null != node.right) {
                stack.addFirst(node.right);
            }
        }
        return ans;
    }
}

思路3:迭代2
就是遍歷到的左節點如果還有右節點的話，怎么處理這個問題，要把這個節點重新放入stack…

class Solution {
   List<Integer>list=new ArrayList();
    public List<Integer> postorderTraversal(TreeNode root) {
      if(root==null) return list;
      Stack<TreeNode>stack=new Stack();
      TreeNode prev = null;
      // Deque<TreeNode> stack = new LinkedList<TreeNode>();
      while(root!=null||!stack.isEmpty()){
          while(root!=null){
              stack.push(root);
              root=root.left;
          }
            root=stack.pop();  
            if (root.right == null || root.right == prev) {
                list.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        } 
      return list;    
    }
}

2021.08.07 （第11天）樹

24 102. 二叉樹的層序遍歷

道理咱們都懂，利用佇列，先入隊根節點，出隊根節點，然后入隊根節點的左節點和右節點，接著出隊，入隊，把這些節點放到一個list里面很簡單，但是怎么實作分層？

可不可以用兩個佇列？
比如我要取出第一個佇列的元素，我就把這個元素的左節點和右節點都放到第二個佇列

自己寫的雙堆疊，雖然不怎么優雅，但是是自己寫的

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode>queue=new  LinkedList<TreeNode>();
         Queue<TreeNode>queue2=new  LinkedList<TreeNode>();
        List<List<Integer>>list=new ArrayList();
        if(root==null)
            return list;
        queue.add(root);
        while(!queue.isEmpty()||!queue2.isEmpty()){
            if(queue2.isEmpty()&&!queue.isEmpty()){
            List <Integer>tempList=new ArrayList();
            while(!queue.isEmpty()){
            TreeNode temp=queue.remove();
            tempList.add(temp.val);
            if(temp.left!=null) queue2.add(temp.left);
            if(temp.right!=null) queue2.add(temp.right);
            } 
            list.add(tempList);         
          }  
          
           if(queue.isEmpty()&&!queue2.isEmpty()){
            List <Integer>tempList=new ArrayList();
            while(!queue2.isEmpty()){
            TreeNode temp=queue2.remove();
            tempList.add(temp.val);
            if(temp.left!=null) queue.add(temp.left);
            if(temp.right!=null) queue.add(temp.right);
            } 
            list.add(tempList);         
          }              
        }
        return list;
    }   
}

封裝一下，它不就優雅了嗎

class Solution {
    List<List<Integer>>list=new ArrayList();
    public List<List<Integer>> levelOrder(TreeNode root) {
         Queue<TreeNode>queue=new  LinkedList<TreeNode>();
         Queue<TreeNode>queue2=new  LinkedList<TreeNode>();      
        if(root==null)
            return list;
        queue.add(root);
        while(!queue.isEmpty()||!queue2.isEmpty()){
            if(queue2.isEmpty()&&!queue.isEmpty())
                 helper(queue,queue2); //取出 queue中的元素，取出節點的左右節點放入queue2               
            if(queue.isEmpty()&&!queue2.isEmpty())
                 helper(queue2,queue); //取出 queue2中的元素，取出節點的左右節點放入queue                         
        }
        return list;
    }  

    public void helper(Queue<TreeNode>queue,Queue<TreeNode>queue2){
            List <Integer>tempList=new ArrayList();
            while(!queue.isEmpty()){
            TreeNode temp=queue.remove();
            tempList.add(temp.val);
            if(temp.left!=null) queue2.add(temp.left);
            if(temp.right!=null) queue2.add(temp.right);
            } 
            list.add(tempList);   
    } 
}

思路二：單佇列實作，就是在每次添加左右節點的時候，先記錄上一層的節點數量

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }
}

參考：

BFS 的使用場景總結：層序遍歷、最短路徑問題

總結：注意實體化佇列不能用 Queuequeue=new Queue();
也不能用Queuequeue=new Deque();因為Queue()和Deque()都是抽象類，不能實體化，而是用的Queuequeue=new LinkedList();

25 104. 二叉樹的最大深度

給定一個二叉樹，找出其最大深度，

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數，

說明: 葉子節點是指沒有子節點的節點，

思路一：廣度優先搜索，在上一題的基礎上，在遍歷每一層時，把記錄層數的變數加1

class Solution {
    public int maxDepth(TreeNode root) {
         Queue<TreeNode>queue=new LinkedList();
         if(root==null) return 0;
         queue.add(root);
         int depth=0;
         while(!queue.isEmpty()){
             depth++;
             int size=queue.size();
             for(int i=0;i<size;i++){
            // for(int i=0;i<queue.size();i++){//這個queue.size()可把我坑慘了，因為queue.size()在彈出，插入的程序中是一直在變的，，，
               TreeNode temp=queue.remove();
               if(temp.left!=null) queue.add(temp.left);
               if(temp.right!=null) queue.add(temp.right);
             }                        
         }
        return depth;
    }
}

思路2：遞回，深度優先
把整樹轉化成每一個小樹，每個數的高度都是1加上它的左右子樹中高度較大的那個

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null)
           return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

再來過分一點的

class Solution {
    public int maxDepth(TreeNode root) {       
        return root==null?0: Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

26 101. 對稱二叉樹

思路1:用佇列，做層序遍歷，把空節點用一個無效節點代替，然后檢查每一層是不是對稱的
參考：【宮水三葉】從「區域」和「整體」兩個角度看待「對稱二叉樹」問題

class Solution {
    int INF = 0x3f3f3f3f;
    TreeNode emptyNode = new TreeNode(INF);
    boolean isSymmetric(TreeNode root) {
        if (root == null) return true;

        Deque<TreeNode> d = new ArrayDeque<>();
        d.add(root);
        while (!d.isEmpty()) {
            // 每次回圈都將下一層拓展完并存到「佇列」中
            // 同時將該層節點值依次存入到「臨時串列」中
            int size  = d.size();
            List<Integer> list = new ArrayList<>();
            while (size-- > 0) {
                TreeNode poll = d.pollFirst();
                if (!poll.equals(emptyNode)) {
                    d.addLast(poll.left != null ? poll.left : emptyNode);
                    d.addLast(poll.right != null ? poll.right : emptyNode);
                }
                list.add(poll.val);
            }
            
            // 每一層拓展完后，檢查一下存放當前層的該層是否符合「對稱」要求
            if (!check(list)) return false;
        }
        return true;
    }

    // 使用「雙指標」檢查某層是否符合「對稱」要求
    boolean check(List<Integer> list) {
        int l = 0, r = list.size() - 1;
        while (l < r) {
            if (!list.get(l).equals(list.get(r))) return false;
            l++;
            r--;
        }
        return true;
    }
}

思路二：遞回

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }
    boolean check(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null) return false;
        if (a.val != b.val) return false;
        return check(a.left, b.right) && check(a.right, b.left);
    }
}

評論區有人說遞回每個節點會遍歷兩次，我也看了半天，覺得確實是這樣，所以，感覺改成下面這樣會更好

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root==null)
            return true;       
        return check(root.left,root.right);       
    }
     boolean check(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null) return false;
        if (a.val != b.val) return false;
        return check(a.left, b.right) && check(a.right, b.left);
    }
}

2021.08.08(第12天)樹

27 226 翻轉一棵二叉樹

思路：運用遞回，從下到上，依次翻轉每一個節點的左節點和右節點

class Solution {
    public TreeNode invertTree(TreeNode root) {
        helper(root);
        return root;
    }
    public void helper(TreeNode root)
    {
        if(root==null)
            return ;      
         helper(root.left);
         helper(root.right);
         TreeNode temp=root.left;
         root.left=root.right;
         root.right=temp;
    }
}

也可以從上到下，依次翻轉每一個節點的左節點和右節點

class Solution {
    public TreeNode invertTree(TreeNode root) {
        helper(root);
        return root;
    }
    public void helper(TreeNode root)
    {
        if(root==null)
            return ;             
         TreeNode temp=root.left;
         root.left=root.right;
         root.right=temp;
         helper(root.left);
         helper(root.right);
    }
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

思路二：迭代，類似層序遍歷，利用佇列，將彈出的節點的左右節點交換

class Solution {
    public TreeNode invertTree(TreeNode root) {
       Queue<TreeNode>queue=new LinkedList();       
       if(root==null)
           return null;
        queue.add(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
               TreeNode temp=queue.remove();
               TreeNode tmp=temp.left;
               temp.left=temp.right;
               temp.right=tmp;
               if(temp.left!=null)  queue.add(temp.left);
               if(temp.right!=null) queue.add(temp.right);
             }                    
        }
      return root;
    }
}

左右節點先交換，然后再存進佇列也是可以的

class Solution {
    public TreeNode invertTree(TreeNode root) {
       Queue<TreeNode>queue=new LinkedList();       
       if(root==null)
           return null;
        queue.add(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
               TreeNode temp=queue.remove();
               if(temp.left!=null) queue.add(temp.left);
               if(temp.right!=null) queue.add(temp.right);             
               TreeNode tmp=temp.left;
               temp.left=temp.right;
               temp.right=tmp;
              
             }                    
        }
      return root;
    }
}

28 112. 路徑總和

給你二叉樹的根節點 root 和一個表示目標和的整數 targetSum ，判斷該樹中是否存在 根節點到葉子節點 的路徑，這條路徑上所有節點值相加等于目標和 targetSum ，
葉子節點 是指沒有子節點的節點，

思路：就是判斷根節點到葉子結點的路徑和
可以拆解一下，拆解成根節點的左節點到葉子結點的和是否等于 targetSum-root.val
以及根節點的右節點到葉子結點的和是否等于 targetSum-root.val
每一層都做這樣的拆分
當根節點為空的時候，root.val都不存在，直接回傳false
最關鍵的點是

 if(root.left==null&&root.right==null)
     return root.val==targetSum; 

左右節點為空，說明是葉子節點，葉子結點的val值是否等于它的父節點傳給他的targetSum，如果為fasle，則會繼續判斷其他路徑，否則，一直回傳true,程式結束，

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
            if(root==null)
                return false;
            if(root.left==null&&root.right==null)//說明是葉子結點
                return root.val==targetSum;                
            if(hasPathSum(root.left, targetSum-root.val))
                return true;
            if(hasPathSum(root.right, targetSum-root.val))
                return true;
            return false;
    }
}

官方的寫法

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}


作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/path-sum/solution/lu-jing-zong-he-by-leetcode-solution/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

思路二：迭代

用兩個佇列，一個佇列存盤節點，另一個佇列存盤該節點之前的和，當遍歷到葉子節點的時候進行判斷

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
            Queue<TreeNode>queue=new LinkedList();
            Queue<Integer>value=new LinkedList();
            if(root==null) return false;
            queue.add(root);
            value.add(root.val);
            while(!queue.isEmpty()){
                TreeNode temp=queue.remove();
                int sum= value.remove();
                if(temp.left==null&&temp.right==null&&sum==targetSum)
                   return true;
                if(temp.left!=null){
                   queue.add(temp.left);
                   value.add(temp.left.val+sum);
                }
                if(temp.right!=null){
                   queue.add(temp.right);
                   value.add(temp.right.val+sum);
                }                  
            }
            return false;
    }
}

2021.08.09(第13天)樹

29 700. 二叉搜索樹中的搜索

給定二叉搜索樹（BST）的根節點和一個值， 你需要在BST中找到節點值等于給定值的節點， 回傳以該節點為根的子樹， 如果節點不存在，則回傳 NULL，

思路1：遞回，從上到下搜索指定節點
沒有用到二叉搜索樹的根節點大于座機誒單，小于右節點的特性，但是理解到了，用遞回做二叉樹的題的時候，可以先想想如果只有一顆二叉樹，一個根節點和它的左右節點，你會怎么處理

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root==null)
           return null;
        if(root.val==val)
            return root;      
        TreeNode temp1= searchBST(root.left,val);
        TreeNode temp2= searchBST(root.right,val);
        if(temp1!=null)
           return temp1;
        if(temp2!=null)
           return temp2;
        return null;
    }
}

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root==null)
           return null;
        if(root.val==val)
            return root;  
        if(root.val>val)    
            return searchBST(root.left,val);
        if(root.val<val)
            return searchBST(root.right,val);       
        return null;
    }
}

我的天啊，這個寫法，愛了愛了

class Solution {
  public TreeNode searchBST(TreeNode root, int val) {
    if (root == null || val == root.val) return root;
    return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
  }
}

思路2：利用二叉樹的前中后序遍歷，層序遍歷，依次匹配節點也是可以的
思路3：迭代

從根節點開始，依次比較val值，大于給定值就往左搜索，小于給定值，就往右搜索

class Solution {
  public TreeNode searchBST(TreeNode root, int val) {
    while(root!=null){
       if(root.val==val)
          return root;
        else if(root.val>val)
          root=root.left;
        else
          root=root.right;
    }
    return null;
  }
}

我的媽呀，官方題解殺我

class Solution {
  public TreeNode searchBST(TreeNode root, int val) {
    while (root != null && val != root.val)
      root = val < root.val ? root.left : root.right;
    return root;
  }
}


作者：LeetCode
鏈接：https://leetcode-cn.com/problems/search-in-a-binary-search-tree/solution/er-cha-sou-suo-shu-zhong-de-sou-suo-by-leetcode/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

30 701. 二叉搜索樹中的插入操作

自己寫的第一版遞回，自己寫的！！！

思路：先想象只有一棵樹，比較和根節點的值的情況，根節點為空，則直接把新的節點當作根節點
插入節點的值大于根節點，則將這個插入節點交給右節點處理
插入節點的值小于根節點，則將這個插入節點交給左節點處理
就相當于是要把新的節點插入到原來的樹中作為某一個節點（這個節點不能是左右節點已經滿了的節點）的左節點或者右節點.

總結：插入的節點必定是一個葉子節點

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
         TreeNode addNode=new TreeNode(val);
         return  root=help(root,addNode,val);                      
    }
    public TreeNode help(TreeNode root,TreeNode addNode,int val){
          if(root==null) 
              return root=addNode;                           
          if(root.val>val)
            root.left= help( root.left,addNode,val);
          if(root.val<=val)  
            root.right =help(root.right,addNode,val);    
          return root;     
    }
}

第二版遞回

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {       
          if(root==null) 
              return root=new TreeNode(val);                           
          if(root.val>val)
            root.left= insertIntoBST( root.left,val);
          if(root.val<=val)  
            root.right =insertIntoBST(root.right, val);    
          return root;                    
    }
}

思路2：迭代
找到某個節點的值大于val值且這個節點的左節點為空，我們就把新節點當作這個節點的左節點
或者某個節點的值小于val值且這個節點的右節點為空，我們就把新節點當作這個節點的右節點

冷知識，while(true)不相信眼淚 ，while(true)里面有return子句之后，while(true)外面居然不用回傳的，，，，，

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {       
         if(root==null)
           return new TreeNode(val);
        TreeNode temp=root;
        while(true) {
            if(temp.val<val){
               if(temp.right==null)
               {
                 temp.right=new TreeNode(val);
                 return root;
               }
               else
                 temp=temp.right;                
            }               
            else{
                 if(temp.left==null)
               {
                 temp.left=new TreeNode(val);
                 return root;
               }
               else
                 temp=temp.left;    
            }        
        }               
    }
}

我也是腦c了，死回圈里面break就好了呀，最后return嘛
看看人家

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode pos = root;
        while (pos != null) {
            if (val < pos.val) {
                if (pos.left == null) {
                    pos.left = new TreeNode(val);
                    break;
                } else {
                    pos = pos.left;
                }
            } else {
                if (pos.right == null) {
                    pos.right = new TreeNode(val);
                    break;
                } else {
                    pos = pos.right;
                }
            }
        }
        return root;
    }
}


作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/solution/er-cha-sou-suo-shu-zhong-de-cha-ru-cao-zuo-by-le-3/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，

2021.08.10 (第14天)樹

31 98. 驗證二叉搜索樹

我的思路是分別驗證左子樹和右子樹
如果左節點小于根節點且左節點的兩個子節點都小于根節點，左子樹成立
如果右節點大于根節點且右節點的兩個子節點都大于根節點，右子樹成立

class Solution {
    public boolean isValidBST(TreeNode root) {
           if(root==null)
              return true;
           return leftValid(root,root.left)&& rightValid(root,root.right)  ;
    }
    public boolean leftValid(TreeNode root,TreeNode child){
              if(root==null||child==null)
                   return true;
              if(root.val<=child.val )
                   return false;
              if(child.right!=null&&child.right.val>=root.val)
                   return false;
              if(child.left!=null&&child.left.val>=root.val)
                   return false;
              return leftValid(child,child.left)&& rightValid(child,child.right)   ;         
    }
     public boolean rightValid(TreeNode root,TreeNode child){
              if(root==null||child==null)
                   return true;
              if(root.val>=child.val )
                   return false;
              if(child.left!=null&&child.left.val<=root.val)
                   return false;
              if(child.right!=null&&child.right.val<=root.val)
                   return false;
              return leftValid(child,child.left)&& rightValid(child,child.right)  ;               
    }
}

判斷條件有疏漏，下面的120和119就被漏判斷了

思路2：中序遍歷

遞回方式

class Solution {
   // int last=Integer.MIN_VALUE;//會報錯，因為給的值可能就是Integer.MIN_VALUE
    long last=Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
           if(root==null)
              return true;
          if(!isValidBST(root.left)) 
             return false;        
           if( root.val<=last)
              return false;
            else
              last=root.val;
           if(!isValidBST(root.right)) 
               return false;
         return true;    
    }
}

last的初始值不能取Integer.MIN_VALUE會報錯，因為給的值可能就是Integer.MIN_VALUE

中序遍歷，迭代版本

class Solution {
    // int last=Integer.MIN_VALUE;
    long last=Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
         Stack<TreeNode>stack=new Stack();
         while(!stack.isEmpty()||root!=null){            
             while(root!=null)
             {
                 stack.push(root);
                 root=root.left;
             }
             root=stack.pop();           
             if(root.val<=last)
                return false;
             else
             {
                 last=root.val;
                 if(root.right!=null)
                    //queue.add(root.right);
                    root=root.right;
                 else
                   root=null;//取出來的結點已經用了，如果該節點沒有右節點，需要把root指向空                                  
             }            
         }
         return true;
    }
}

我是傻逼嗎，代碼簡化如下

class Solution {
    // int last=Integer.MIN_VALUE;
    long last=Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
         Stack<TreeNode>stack=new Stack();
         while(!stack.isEmpty()||root!=null){            
             while(root!=null)
             {
                 stack.push(root);
                 root=root.left;
             }
             root=stack.pop();           
             if(root.val<=last)
                return false;                         
            last=root.val;                         
            root=root.right;//取出來的結點已經用完了，需要把root指向空右節點，然后把右節點的左節點壓入堆疊中                                                                
         }
         return true;
    }
}

思路3 設定左右結點的取值范圍，

因為結點取值可能是Integer的最大值和最小值，所以我們設定的上限和下限應該是Long的最大值和最小值
左節點的取值范圍是最小值到根節點的值，且不能等于根節點的值
右節點的取值范圍是根節點的值到最大值，且不能等于根節點的值

class Solution {
    long low=Long.MIN_VALUE;
    long upper=Long.MAX_VALUE;
    public boolean isValidBST(TreeNode root) {
         if(root==null)
            return true;   
        return   isValidBST( root.left,low,root.val)&&  isValidBST( root.right,root.val,upper)  ;
    }
    public boolean  isValidBST( TreeNode root,  long low, long upper){
        if(root==null)
          return true;
        if(root.val>=upper||root.val<=low)
          return false;
        return  isValidBST( root.left,low,root.val)&&  isValidBST( root.right,root.val,upper);
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }
}

32 653. 兩數之和 IV - 輸入 BST

給定一個二叉搜索樹 root 和一個目標結果 k，如果 BST 中存在兩個元素且它們的和等于給定的目標結果，則回傳 true，

思路1：中序遍歷+雙指標

因為BST即排序二叉樹的中序遍歷是升序排列的
所以我們可以先來個中序遍歷，把結點的值都存進一個list，然后利用雙指標在排序陣列中查找目標和

class Solution {
     List<Integer>list=new ArrayList();
    public boolean findTarget(TreeNode root, int k) {
         inOrder(root);
         int i=0;int j=list.size()-1;
         while(i<j){
             if(list.get(i)+list.get(j)>k)
                j--;
             else if(list.get(i)+list.get(j)<k)
                i++;
            else 
                return true;
         }
         return false; 
    }
    public void inOrder(TreeNode root){
        if(root==null)
         return ;
         inOrder(root.left);
         list.add(root.val);
         inOrder(root.right);
    }
}

思路2 HashSet
從上到下遍歷結點，每遍歷到一個結點，就在set里面去找有內有對應的結點加起來等于k,有就直接回傳true
沒有就把這個結點加入set中，繼續遍歷下一個結點，

class Solution {
    Set<Integer>set=new HashSet();
    public boolean findTarget(TreeNode root, int k) {
      if(root==null)
        return false;
      if(set.contains(k-root.val))
        return true;
      set.add(root.val);
      return  findTarget(root.left, k)||findTarget(root.right, k);
    }    
}

思路3 ：BFS+Set

public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set < Integer > set = new HashSet();
        Queue < TreeNode > queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            if (queue.peek() != null) {
                TreeNode node = queue.remove();
                if (set.contains(k - node.val))
                    return true;
                set.add(node.val);
                queue.add(node.right);
                queue.add(node.left);
            } else
                queue.remove();
        }
        return false;
    }
}

33 235. 二叉搜索樹的最近公共祖先

給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先

思路1，遞回
判斷pq與根結點的位置關系

p q中如果有一個是根節點，則回傳根節點
p q 如果位于根節點的兩邊 則回傳根節點
p q如果都位于根節點的左邊，則向左邊繼續查找
p q如果都位于根節點的右邊，則向右邊繼續查找

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {       
        if(root==null||(p.val<=root.val&&q.val>=root.val)||(p.val>=root.val&&q.val<=root.val))//pq位于根節點的兩邊，則回傳根節點
           return root;
        if(p.val<root.val&&q.val<root.val)
           return  lowestCommonAncestor(root.left,  p, q) ;
        return  lowestCommonAncestor(root.right,  p, q) ;
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        return root;
    }
}

思路2：迭代

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {       
        while(true){
            if(p.val>root.val&&q.val>root.val)
               root=root.right;
            else if(p.val<root.val&&q.val<root.val)
               root=root.left;
            else
              break;
        }
        return root;
    }
}

這，，，，，，，，，,注意第二行用p和q判斷都可以

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {       
        while ((root.val - p.val) * (root.val - q.val) > 0)
            root = p.val < root.val ? root.left : root.right;
        //如果相乘的結果是負數，說明p和q位于根節點的兩側，如果等于0，說明至少有一個就是根節點
        return root;
    }
}

思路3：兩次遍歷，就是分別找出找到p和q需要經過的路徑，把路徑上的結點存起來，然后比較兩個路徑的最后一個相同結點

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path_p = getPath(root, p);
        List<TreeNode> path_q = getPath(root, q);
        TreeNode ancestor = null;
        for (int i = 0; i < path_p.size() && i < path_q.size(); ++i) {
            if (path_p.get(i) == path_q.get(i)) {
                ancestor = path_p.get(i);
            } else {
                break;
            }
        }
        return ancestor;
    }

    public List<TreeNode> getPath(TreeNode root, TreeNode target) {
        List<TreeNode> path = new ArrayList<TreeNode>();
        TreeNode node = root;
        while (node != target) {
            path.add(node);
            if (target.val < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        path.add(node);
        return path;
    }
}


作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/solution/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-26/
來源：力扣（LeetCode）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，