LeetCode

• Self use notes
  

array

27. Remove elements

• Give you an array num and a value val. you need to remove all elements with a value equal to Val in place and return the new length of the array after removal.
• Instead of using extra array space, you must use only O(1) extra space and modify the input array in place.
• The order of elements can be changed. You don't need to consider the elements in the array that exceed the new length.
  
  
• Violent algorithm

• C

  • Analysis: the outer loop controls the array judgment, and the inner loop is used to cover the array elements

  int removeElement(int* nums, int numsSize, int val) {
    int i, j;
    int len = numsSize;
    for (i = 0; i < len; i++) {
        if (nums[i] == val) {
            j = i+1;
            while (j < len) {
                nums[j-1] = nums[j];//j-1 is to prevent subscript out of bounds
                j++;
            }
            len--;
            i--;//In the case of len -- i must--
        }
    }
    return len;
  }

• JAVA

  /*
  Time complexity: O(n^2)
  Space complexity: O(1)
  */
  public int removeElement(int[] nums, int val) {
    int n = nums.length;
    for(int i=0;i<n;i++){
        if(nums[i]==val){
            for(int j=i+1;j<n;j++){
                nums[j-1] = nums[j]; // Be careful to cross the border
            }
            i--;// Because the values after subscript i move forward by one bit, I also moves forward by one bit
            n--;
    
        }
    }
    
    return n;
    }

• Double finger needle method (fast and slow pointer method):
• Complete the work of two for loops under one for loop through a fast pointer and a slow pointer

• C

  int removeElement(int* nums, int numsSize, int val){
    int solw = 0,fast;
    for(fast=0;fast<numsSize;fast++){
        if(val!=nums[fast]){
            nums[solw++] = nums[fast];
        }
  
    }
    return solw;
  }

• JAVA

  // Time complexity: O(n)
  // Space complexity: O(1)
  public int removeElement2(int[] nums, int val) {
    int slowIndex = 0;
    for(int fastIndex = 0; fastIndex< nums.length;fastIndex++){
        if(val != nums[fastIndex]){
            nums[slowIndex++] = nums[fastIndex];
        }
    }
    return slowIndex;
  }

35. Search insertion position

• Given a sort array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order.
• You can assume that there are no duplicate elements in the array.
• binary search
• C

int searchInsert(int* nums, int numsSize, int target){
      int low = 0, high = numsSize-1;
    int mid;
    while (low <= high) {
        mid = low + (high - low) / 2;
        if (target > nums[mid])
            low = mid + 1;
        else if (target < nums[mid])
            high = mid - 1;
        else
            return mid;
    }
    return high+1;
}

• JAVA

  public int searchInsert(int[] nums, int target) {
    int n = nums.length;
    int left = 0,right = n -1; // Define that the target is in the left closed and right closed interval, [left, right]
    while(left<=right) { // When left==right, the interval [left, right] is still valid
        int mid = left + ((right - left) / 2); // Prevent overflow, equivalent (left+right)/2
        if (target < nums[mid]) {
            right = mid - 1;// target is in the left interval, so [left, middle - 1]
        } else if (target > nums[mid]) {
            left = mid + 1;
        } else {  // nums[middle] == target
            return mid;
        }
    }
    return right+1;
    /*
    Deal with the following four situations respectively
    1.Target value precedes all elements of the array [0, - 1]
        target = -1,nums = [1,3,5,7]
        First cycle
        right = 3,left = 0,mid = 1
        target < nums[1] = 3 --> right = mid -1 = 0
        Second cycle
        right = 0,left = 0,mid = 0
        target < nums[0] = 1 --> right = mid -1 = -1
        At the end of the cycle, right+1 = 0 is returned
    2.The target value is equal to an element in the array return middle;
    3.The target value is in the middle of the array [left, right], return right + 1
        target = 4,nums = [1,3,5,7]
        First cycle
        right = 3,left = 0,mid = 1
        target > nums[1] = 3 --> left = mid + 1 = 1
        Second cycle
        right = 3,left = 1,mid = 2
        target < nums[2] = 5 --> right = mid -1 = 1
        At the end of the cycle, right+1 = 2 is returned
    4.Target value after all elements of the array [left, right], return right + 1
         */
    }

209. Minimum length subarray

• Given an array containing positive integers and a positive integer target.
  Find out the continuous sub array [numsl, numsl + 1,..., numsr-1, numsr] with the smallest length satisfying its sum ≥ target in the array, and return its length. If there is no eligible subarray, 0 is returned.
• Violent algorithm

• analysis:

  • Take the interval from i to j, then sum and judge the interval
  • j-i+1 is the current number of elements from i to j
  • The judgment of ternary expression is to judge whether the old length is larger than the new length?, Because find the minimum length

• C

  int minSubArrayLen(int target, int* nums, int numsSize){
    int i, j;
    int sum;
    int subLen;//Used to identify the new length
    int result = INT_MAX;//It is used to identify the old length. A maximum value should be taken here
    for (i = 0; i < numsSize; i++) {
        sum = 0;
        for (j = i; j < numsSize; j++) {
            sum += nums[j];
            if (sum >= target) {
                subLen = j - i + 1;//Gets the length of the subarray contained in the sum
                result = result > subLen ? subLen : result;//Judge whether the old length is greater than the new length
                break;
            }
        }
    }
    return result==INT_MAX ? 0:result;//Prevent the sum of all elements from being greater than target
  }

• JAVA

  //Violent solution
  //Time complexity: O(n^2)
  //Space complexity: O(1)
  public int minSubArrayLen(int target, int[] nums) {
      int result = Integer.MAX_VALUE; // Take the maximum value of an array that cannot be exceeded
      int sum = 0; // Sum of subsequences
      int subLength = 0; // Length of subsequence
      for(int i=0;i<nums.length;i++){
          sum = 0;
          for(int j=i;j<nums.length;j++){
              sum+=nums[j];
              if(sum>=target){
                  subLength = j-i+1; // Take the length of subsequence
                  result = result<subLength?result:subLength; // Compare with the previous length
                  break; // Because we are looking for the shortest subsequence that meets the conditions, we break once the conditions are met
              }
          }
      }
      // If the result is not assigned, it returns 0, indicating that there are no qualified subsequences
      return result == Integer.MAX_VALUE ? 0:result;
  }

  • sliding window

    • To realize the sliding window in this topic, the following three points are mainly determined:
      1. What is in the window?
      2. How to move the starting position of the window?
      3. How to move the end position of the window
      A window is a continuous subarray with the smallest length that satisfies and > = target;
      How to move the starting position of the window: if the value of the current window is > target, the window will move forward (i.e. shrink the window)
      How to move the end position of the window: the end position of the window is the pointer to traverse the array, and the start position is the start position of the array.

  • JAVA

    //sliding window
    /*
    The beauty of sliding window is that according to the current subsequence and size,
    Continuously adjust the starting position of the subsequence. Thus, the violent solution of O(n^2) is reduced to O(n).
     */
    public int minSubArrayLen_2(int target, int[] nums) {
    int result = Integer.MAX_VALUE;
    int sum = 0;//Sum of sliding window values
    int i = 0;//Start position of sliding window
    int subLength = 0;//Length of sliding window
    for(int j=0;j< nums.length;j++){
        sum+=nums[j];
        //Use while to update i (starting position) every time and constantly compare whether the subsequence meets the conditions
        while(sum>=target){
            subLength = (j - i + 1);//Take the length of subsequence
            result = result < subLength? result:subLength;
            sum -= nums[i++];//Subtract the first number, the number of numbers in the window is - 1, and i slides to the i + + position
        }
    }
    return result == Integer.MAX_VALUE ? 0 : result;
    
    /*
    nums[] = 2 , 3 , 1 , 2 , 4 , 3    target = 7
     Subscript: 0 1 2 3 4 5
    sum = 0;i = 0;subLength = 0;
    1.       ij(Point to subscript 0) - > sum = 0 + 2 = 2
    2.       i   j          --> sum = 2+3 = 5
    3.       i       j          --> sum = 5+1 = 6
    4.       i           j          --> sum = 6+2 = 8
    while-->subLength = j-i+1 = 3-0+1 = 4
         -->result = Max < 4 ? Max:4 = 4
         -->sum -= nums[i++] = sum - nums[0] = 8-2 = 6
         -->      i(Move forward I, i.e. the window shrinks)
     ...
     ...
     */
    }

• C

int minSubArrayLen(int target, int* nums, int numsSize){
    int i = 0,j;
    int result = INT_MAX;
    int sublen = 0;
    int sum = 0;
    for(j=0;j<numsSize;j++){
        sum += nums[j];
        while(sum>=target){
            sublen = j-i+1;
            result = result > sublen ? sublen:result;
            sum -= nums[i++];
        }
    }
    return result==INT_MAX?0:result;
}

59. Spiral matrix II

• Give you a positive integer n and generate an n x n square matrix containing all elements from 1 to n2, and the elements are spirally arranged in clockwise order.

  public int[][] generateMatrix(int n) {
      int[][] nums = new int[n][n];
      int startX = 0,startY = 0;//Define the starting position of each cycle, such as (0,0), (1,1)
      int loop = n / 2;//Cycle several times for each cycle. If n=3 is an odd number, loop=1 only cycles once,
                      //The values in the middle of the matrix need to be processed separately
      int mid = n / 2;//The middle position of the matrix, such as n=3, is (1,1), n = 5 -- > (2,2)
      int count = 1;//Variables assigned to the matrix
      int offset = 1;//For each loop, you need to control the length of each edge traversal
      int i,j;
      while(loop--!=0){
          i = startX;
          j = startY;
      
          //The following four for's are simulated turns
          /*
          →   →   ↓
          ↑   →   ↓
          ↑   ←   ←
           */
          //Up from left to right
          for(j = startY;j<startY+n-offset;j++){
              nums[startX][j] = count++;
          }
      
          //Right column from top to bottom
          for(i = startX;i<startX+n-offset;i++){
              nums[i][j] = count++;
          }
      
          //Analog downlink from right to left
          for(;j>startY;j--){
              nums[i][j] = count++;
          }
      
          //Simulate left column from bottom to top
          for(;i>startX;i--){
              nums[i][j] = count++;
          }
      
          // At the beginning of the second lap, the starting position should be increased by 1 respectively, 
          //For example, the starting position of the first circle is (0, 0), and the starting position of the second circle is (1, 1)
          /*
          If n=4:
          First lap:
              0   1   2   3
          0   →   →   →   ↓
          1   ↑           ↓
          2   ↑           ↓
          3   ↑   ←   ←   ←
          -->Then the first circle starts from (0,0)
          Second lap:
              1   2
          1   →   ↓
          2   ↑   ←
          -->Then the second circle starts from (1,1)
           */
          startX++;
          startY++;
      
          // offset controls the traversal length of each edge in each circle
          // If n=4, the length of the first row in the first circle = 4, and the length of the first row in the second circle is 4-2 = 2
          /*
          First lap:
          →   →   →   ↓
          ↑           ↓
          ↑           ↓
          ↑   ←   ←   ←
          Second lap:
          →   ↓
          ↑   ←
           */
          offset += 2;
      }
      
      // If n is an odd number, the middle position of the matrix needs to be assigned separately
      /*
      If n=3, the center point is (1,1)
      n=5,The center point is (2,2)
       */
      if (n % 2==1) {
          nums[mid][mid] = count;
      }
      
      return nums;
      }

• Code push map
  *

  217. There are duplicate elements

• Given an integer array, determine whether there are duplicate elements. If a value exists and appears in the array at least twice, the function returns true. If each element in the array is different, false is returned.

• analysis:

  • Sort the array first
  • Then you just need to judge whether the adjacent elements in the array are repeated
• C

int cmp(const void* _a, const void* _b) {
    int a = *(int*)_a, b = *(int*)_b;
    return a - b;
}

bool containsDuplicate(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);//Quick sort
    for (int i = 0; i < numsSize - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return true;
        }
    }
    return false;
}

53. Longest subsequence and?

• Given an integer array nums, find a continuous sub array with the largest sum (the sub array contains at least one element) and return its maximum sum.

• analysis:

  • dynamic programming

• C

  int maxSubArray(int* nums, int numsSize) {
    int preSum = 0;//Before and
    int maxSum = nums[0];//Maximum sum
    for (int i = 0; i < numsSize; i++) {
        preSum = fmax(preSum + nums[i], nums[i]);//Maximum function
        maxSum = fmax(preSum, maxSum);
    }
    return maxSum;
  } 

Linked list

142. Circular linked list II

• Given a linked list, return the first node from the linked list into the ring. If the linked list is acyclic, null is returned.
  In order to represent the rings in a given linked list, we use the integer pos to represent the position where the tail of the linked list is connected to the linked list (the index starts from 0). If pos is - 1, there is no ring in the linked list. Note that pos is only used to identify the ring and is not passed to the function as a parameter.
• Note: it is not allowed to modify the given linked list.
• analysis:

• Judge whether there are links in the linked list

  • Define slow, and the fast pointer points to head
  • The slow pointer takes one step and the fast pointer takes two steps
  • If there is a ring, fast and slow will meet; If there is no loop, there is fast - > next = null, that is, jump out of the loop

• If there is a ring, how to find the entrance of this ring

  • Set the number of nodes of the head node -- > ring entry node as x
  • Ring entry node -- > the number of nodes of the encounter node (fast, slow) is y

  • Encounter node -- > the number of nodes of the ring entry node is z

    • When meeting: the number of nodes passed by the slow pointer = x+y, fast=x+y+n(y+z)
      n is fast. It takes n cycles to meet slow in the ring, and y+z is the number of nodes in the ring
    • fast = slow*2, that is, the number of fast passes is twice that of slow
      --> (x+y)*2 = x+y+n(y+z)
      --> (x+y) = n(y+z)
      --> x = n(y+z) - y
      --> x = (n-1) (y+z) + z
  • When n=1, x=z
  • When n > 1, the fast pointer encounters slow after n turns in a circle

• code

  public ListNode detectCycle(ListNode head) {       
    ListNode fast = head;//Define speed pointer
    ListNode slow = head;
    while( fast!=null && fast.next!=null){
        slow = slow.next;//Slow the pointer one step
        fast = fast.next.next;//Fast pointer, take two steps
        //Meet quickly and slowly
        if(slow == fast){
            ListNode index1 = fast;
            ListNode index2 = head;
            while(index1 != index2){
                index1 = index1.next;
                index2 = index2.next;
            }
            return index2; //Return entry
        }
    
    }
    return null;
    }

• Code push map
  

203. Remove linked list elements

• Give you a head node of the linked list and an integer val
• Please delete all nodes in the linked list Val = = Val node and returns a new header node.
  
  

• iteration

    /*
    Because the header node may be deleted when it meets the conditions
    For example: val = 2
    head(2)-->1-->4-->null
    ==>
    dummyHead-->head(2)-->1-->4-->null
    Then just point the virtual node dummyHead to the head Next
    ==>
    dummyHead   head(2)-->1-->4-->null
            |             ↑
            |_____________|
     */
  

public ListNode removeElements(ListNode head, int val) {
    ListNode dummyHead = new ListNode();//Set a virtual head node
    dummyHead.next = head;//Point the virtual node to the head node
    ListNode cur = dummyHead;
    
    while(cur.next!=null){
        if(cur.next.val==val){
            cur.next = cur.next.next;
    
        }else{
            cur = cur.next;
        }
    }
    
    //Of course, the final linked list returned starts from the next location of the virtual node
    return dummyHead.next;
    }

• recursion

  public ListNode removeElements2(ListNode head,int val){
    if(head==null){
        return head;
    }
    head.next = removeElements(head.next, val);
    return head.val==val?head.next : head;//When the condition is true, head Linked list after next
    }

  206. Reverse linked list

• Give you the head node of the single linked list. Please reverse the linked list and return the reversed linked list.

• analysis:

  1. Define three pointers: pre, curr and temp, which respectively point to the predecessor node (null) of head, the head node and the successor node of curr.
  2. Judge whether to reverse when curr is not empty
  3. Three pointers can be moved backward at the same time

   /*
        For example:
        null    1----->2----->3----->4
         ↑      ↑      ↑
        pre     curr  temp
        1.          1<-----2      3----->4
                    ↑      ↑      ↑
                   pre     curr  temp
        2.          1<-----2<------3      4
                           ↑       ↑      ↑
                           pre    curr   temp
        3.          1<-----2<------3<------4
                                   ↑       ↑      ↑
                                   pre    curr   temp
         */

• code

  public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
  
        ListNode pre = null;
        ListNode curr = head;//Point to head node
        ListNode temp = null;//Save the next node of curr
        while(curr!=null){
            temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
        }
        return pre;
  
    }

707. Design linked list

• Design the implementation of linked list. You can choose to use single linked list or double linked list. A node in a single linked list should have two attributes: val and next. val is the value of the current node, and next is the pointer / reference to the next node. If you want to use a two-way linked list, you also need an attribute prev to indicate the previous node in the linked list. It is assumed that all nodes in the linked list are 0-index.

• Implement these functions in the linked list class:

  1. get(index): get the value of the index node in the linked list. Returns - 1 if the index is invalid.
  2. addAtHead(val): add a node with value val before the first element of the linked list. After insertion, the new node will become the first node of the linked list.
  3. addAtTail(val): append the node with the value of val to the last element of the linked list.
  4. addAtIndex(index,val): add a node with value val before the index node in the linked list. If the index is equal to the length of the linked list, the node will be attached to the end of the linked list. If the index is greater than the length of the linked list, the node will not be inserted. If the index is less than 0, the node is inserted in the header.
  5. Delete atindex (index): if the index is valid, delete the index node in the linked list.

• code

  //Linked list class
  public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
  }
  
  class MyLinkedList{
  /*    public static void main(String[] args) {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addAtHead(1);
        linkedList.addAtTail(3);
        linkedList.addAtIndex(1,2);
        linkedList.get(1);
        linkedList.deleteAtIndex(1);
        linkedList.get(1);
    }
    */
    int size;
    ListNode head;//Virtual head node
    public int get(int index) {
        if(index>=size||index<0) return -1;//Invalid index returned
  
        ListNode curr = head;
        for(int i=0;i<index+1;++i){//Traverse to the node indicated by index
            curr = curr.next;
        }
        return curr.val;
    }
  
    public void addAtHead(int val) {
        ListNode curr = new ListNode(val);
        curr.next = head.next;
        head.next = curr;
        size++;//Self increasing length
    }
  
    public void addAtTail(int val) {
        ListNode curr = head.next;
        ListNode addNode = new ListNode(val);
        while(curr.next!=null){//Traverse to the end of the linked list
            curr = curr.next;
        }
  
        curr.next = addNode;
        size++;//Self increasing length
    }
  
    public void addAtIndex(int index, int val) {
  
        if(index>size)
            return ;
        if(index<0)
            index = 0;
  
        ListNode curr = head;
        for(int i=0;i<index;i++){//Traverse to the node before index subscript
            curr = curr.next;
        }
  
        ListNode addNode = new ListNode(val);
        addNode.next = curr.next;
        curr.next = addNode;
        size++;
    }
  
    public void deleteAtIndex(int index) {
        if(index>=size||index<0){//index is not valid
            return ;
        }
  
        ListNode curr = head;
        while(index--!=0){//Traverse to the previous node of the node to be deleted
            curr = curr.next;
        }
        curr.next = curr.next.next;
        size--;//Length self reduction
    }
  }

19. Delete the penultimate node of the linked list

• Give you a linked list, delete the penultimate node of the linked list, and return the head node of the linked list.

• analysis:

  • Using fast and slow pointers, fast takes n steps first, and then the two pointers traverse at the same time
  • When fast points to null, the element referred to by slow is the node to be deleted
  • If a virtual header node is used, when fast points to null, slow - > next is the node to be deleted, which is the same as deleting directly
  • JAVA

  public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;//Set virtual head node
        ListNode fast = dummyHead;
        ListNode slow = dummyHead;
        int temp = n;
        while(temp-- > 0){//fast n steps first
            fast = fast.next;
        }
        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
  
        return dummyHead.next;
    }

Interview question 02.07 Linked list intersection

• Here are the head nodes headA and headB of the two single linked lists. Please find and return the starting node where the two single linked lists intersect. If the two linked lists have no intersection, null is returned.

• analysis:

  • First traverse the long linked list and align it with the end of the short linked list

  • For example:
    a1->a2->a3->c1->c2->c3

          b1->b2->c1->c2->c3

  • Then the two linked lists traverse backward at the same time. If the nodes are equal (non equal values), it returns; Otherwise, null

• JAVA

  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
     ListNode curA = headA;
     ListNode curB = headB;
     int lenA = 0,lenB = 0;
     while(curA!=null){//Find the length of linked list A
         lenA++;
         curA = curA.next;
     }
     while(curB!=null){//Find the length of linked list B
         lenB++;
         curB = curB.next;
     }
     curA = headA;//Re point the pointer to the header node
     curB = headB;
     int gap = lenA-lenB;//Length difference
     if(lenB>lenA){//If the length of linked list b is large
         curB = headA;
         curA = headB;
         gap = lenB - lenA;
     }
    
     while(gap-->0){//Let Cura (longer length) traverse to the same starting point as curb (shorter length) (align the end position)
         curA = curA.next;
     }
    
     while(curA!=null){
         if(curA==curB){//Same node
             return curA;
         }
         curA = curA.next;
         curB = curB.next;
     }
     return null;
    }

Hashtable

1. Sum of two numbers

• Given an integer array nums and an integer target value target, please find the two integers with and as the target value target in the array and return their array subscripts.
• You can assume that each input will correspond to only one answer. However, the same element in the array cannot appear repeatedly in the answer.
• You can return answers in any order.

• analysis:

  1. Use map combined with storage. key is the value and value is the subscript
  2. Judgment: if the value of target num [i] exists in the map (i.e. the difference of another number), the map is returned Get (target num [i]) and the subscript of I; Otherwise, it is stored in the map. This ensures that the elements are not repeated.

   /*
   For example:
   nums = [1,2,3,4]    target = 5
   1.  nums[i] = nums[0] = 1   target-nums[0] = 5-1 = 4((none)     
     map.put(nums[0],0)--> map = {{1,0}}
   2.  nums[i] = nums[1] = 2   target-nums[1] = 5-2 = 3((none)     
      map.put(nums[1],1)--> map = {{1,0},{2,1}}
   3.  nums[i] = nums[2] = 3   target-nums[2] = 5-3 = 2((yes)
     return new int[]{map.get(2),2}  = {1,2}
  */

public int[] twoSum(int nums[],int target){
     //The key of map is the value, and value is the subscript
     Map<Integer,Integer> map = 
             new HashMap<Integer,Integer>();
     for(int i=0;i<nums.length;i++){
         if(map.containsKey(target-nums[i])){
              //Returns an array of subscripts
             return new int[]{map.get(target-nums[i]),i};
         }
         map.put(nums[i],i);//Insert the qualified number into the table
     }
     return new int[0];
    }

15. Sum of three

• Give you an array num containing n integers. Judge whether there are three elements a, b and c in num, so that a + b + c = 0? Please find all triples with sum 0 and no repetition.
• Note: the answer cannot contain duplicate triples.

• analysis

  1. Sort the array first to facilitate repetition
  2. Use double pointers left and right, with left pointing to the left end (i+1) and right pointing to the right end (length-1)
  3. There are three pointers i, left and right. If the last two pointers are close to each other, you can judge the sum of the indexes of the three pointers

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> ls = new ArrayList<List<Integer>>();
    //Array sorting
    Arrays.sort(nums);
    for(int i=0;i<nums.length;i++){
        if(nums[i]>0){
            return ls;
        }
    
        //De duplication method
        if(i>0&&nums[i]==nums[i-1]){
            continue;
        }
    
        int left = i+1;//Left pointer
        int right = nums.length -1;//Right pointer
        while(left<right){
            if(nums[i]+nums[left]+nums[right]>0){//When the value is greater than zero, it means that the number is large
                right--;
            }else if(nums[i]+nums[left]+nums[right]<0){//Similarly, the value is small
                left++;
            }else{
                List<Integer> result = new ArrayList<Integer>();
                result.add(nums[i]);
                result.add(nums[left]);
                result.add(nums[right]);
                ls.add(result);//Add a triple
                while(left<right&&nums[right]==nums[right-1])
                    right--;
                while(left<right&&nums[left]==nums[left+1])
                    left++;
                //Double pointers close together at the same time
                right--;
                left++;
    
            }
        }
    
    }
    return ls;
    }

202. Happy number

• Write an algorithm to judge whether a number n is a happy number.
• "Happy number" is defined as:
• For a positive integer, replace the number with the sum of the squares of the numbers at each position each time.
• Then repeat the process until the number becomes 1, or it may be an infinite loop, but it never becomes 1.
• If it can be changed to 1, then this number is the number of happiness.
  If n is a happy number, return true; If not, false is returned.

• analysis:

  • Store the sum of squares of each calculation into HashSet
  • Judge: if there is a duplicate sum, return false; Conversely, return true

  public boolean isHappy(int n) {
    Set<Integer> set = new HashSet<Integer>();
    while(true){
        int sum = getSum(n);//The sum value is updated each time
        if(sum==1){
            return true;
        }
    
        if(set.contains(sum)){//When there is a duplicate sum in the collection, this number is not a happy number
            return false;
        }else {
            set.add(sum);
        }
        n = sum;
    }
    }
  
    //Take the sum of the singular numbers in each bit of the value
    int getSum(int n){
        int sum = 0;
        while(n>0){
            sum += (n%10) * (n%10);//Sum of squares
            n /= 10;
        }
        return sum;
    }

242. Ectopic words with valid letters

• Given two strings s and t, write a function to judge whether t is an alphabetic ectopic word of s.

• analysis:

  • Ectopic words: the letters are the same, the order is different, and the length of ectopic words must be the same
  • Define the record array to record the number of occurrences of the string s character. The size of the array is 26

  • Traverse the string s and record the number of letters (+ 1), arr_s[i] - 'a' is the position of the mapped letter

    • If 'b' - 'a' = 1, that is, the subscript of b is 1. Similarly, the subscript of a is 0
  • Similarly, traverse the string t and record the number of occurrences of characters (- 1)
  • Judge that if all the elements of the record array are 0, it is an ectopic word; On the contrary, it is not
• code

public boolean isAnagram(String s, String t) {
    if(s.length()!=t.length()){//Comparison length
        return false;
    }
    int[] record = new int[26];//Define an array to record the number of characters in the string s
    char[] arr_s = s.toCharArray();
    for(int i=0;i<arr_s.length;i++){
        record[arr_s[i] - 'a']++;//Number of occurrences of mapped characters
        /*
        For example:
        arr[0] = 'b';
        -->
        record[arr[i] - 'a'] = record['b' - 'a'] = record[1];
        record[1]++  =  1;  ,
        That is, b appears once in the string s, and the subscript of b is 1,
        Similarly, the subscript of a is 0
         */
    }
    char[] arr_t = t.toCharArray();
    for(int i=0;i<arr_t.length;i++){
        record[arr_t[i] - 'a']--;//The characters appearing in the string t are mapped, and then mapped in the record table and - 1
    }
    for(int i=0;i<26;i++){
        if(record[i] != 0){
            //Judge that if there is a non-zero number of times in the array, it is not an ectopic word
            return false;
        }
    }
    //If all the elements in the record are zero, the two mappings cancel each other, which is an ectopic word
    return true;
    }

304. Intersection of two arrays

• Given two arrays, write a function to calculate their intersection.
• Example 1:
  Input: nums1 = [1,2,2,1], nums2 = [2,2]
  Output: [2]
• Example 2:
  Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
  Output: [9,4]
• Each element in the output result must be unique.

• We can ignore the order of output results.

  public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set1 = new HashSet<Integer>();
    Set<Integer> set2 = new HashSet<Integer>();
    //Load the arrays into the collection separately
    for(int num:nums1){
        set1.add(num);
    }
    for(int num:nums2){
        set2.add(num);
    }
    return getIntersection(set1,set2);
  }
  public int[] getIntersection(Set<Integer> set1,Set<Integer> set2){
    if(set1.size()>set2.size()){//Traverse the one with the smaller length of the set
        return getIntersection(set2,set1);
    }
    Set<Integer> intersectionSet = new HashSet<Integer>();
    for(int num:set1){//Determine whether there are the same numbers
        if(set2.contains(num)){
            intersectionSet.add(num);
        }
    }
    
    //Store the collection into an array and return
    int[] intersection = new int[intersectionSet.size()];
    int index = 0;
    for(int num:intersectionSet){
        intersection[index++] = num;
    }
    return intersection;
  }

383. Ransom letter

• Given a ransom string and a magazine string, judge whether the first string ransom can be composed of the characters in the second string magazines. If it can be constructed, return true; Otherwise, false is returned.
• (Title Description: in order not to expose the handwriting of the ransom letter, search the required letters from the magazine to form words to express their meaning. Each character in the magazine string can only be used once in the ransom letter string.)

• analysis:

  1. Establish two arrays with length of 26, and map the occurrence times of letters in r and m strings to the array
  2. Judgment: if r [i] > m [i], it means that r cannot be listed by M

  public boolean canConstruct(String ransomNote, String magazine) {
    int[] ransomNote_record = new int[26];//The default value is 0
    int[] magazine_record = new int[26];
    
    for(int i=0;i<ransomNote.length();i++){//Mapping alphabet
        ransomNote_record[ransomNote.charAt(i)-'a']++;
    }
    for(int j=0;j<magazine.length();j++){
        magazine_record[magazine.charAt(j)-'a']++;
    }
    for(int i=0;i<ransomNote_record.length;i++){//Compare the number of stored letters
        //If the number of letters in r is greater than the number of letters corresponding to m, r cannot be listed by M
        if(ransomNote_record[i]>magazine_record[i]){
                return false;
        }
    }
    return true;
    
    }

454. Adding four numbers II

• Given four array lists containing integers a, B, C, D, calculate how many tuples (i, j, k, l) there are, so that A[i] + B[j] + C[k] + D[l] = 0.
• In order to simplify the problem, all a, B, C and d have the same length N, and 0 ≤ n ≤ 500. All integers range from - 228 to 228 - 1, and the final result will not exceed 231 - 1.

• analysis:

  1. Use map to traverse arrays A and B first. key is the sum of A+B, and value records the number of times the sum appears
  2. Then traverse C and D. when there are elements of 0-[c+d] (C and D are elements in C and D) in the original map, the number of times can be recorded
  3. Both time and space are o(n^2)

   /*
   For example:
   nums1=[1,2]  nums2=[2,1]    nums3=[-1,1]     nums4=[-2,1]
   map --> {{3,2},{2,1},{4,1}} -->That is, 3 occurs twice, 2 once and 4 once
   1.  0-(-1+-2) = 3 -->true
     temp += 2 = 2
   2.  0-(-1+1)  = 0 -->false
   3.  0-(1-2)   = 1 -->true
     temp += 1 = 3
     ......
  
  */

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
     //Define the number of occurrences of map, key a+b and value a+b
     Map<Integer,Integer> map =
             new HashMap<Integer,Integer>();
     //Traverse the first two arrays
     for(int a:nums1){
         for(int b:nums2){
             //Judge whether a+b has occurred: If yes, + 1; Conversely, count from 0
             int count = 
                     map.containsKey(a+b) ? map.get(a+b):0;
             map.put(a+b,count+1);
         }
     }
     int temp = 0;//Record the number of times a+b+c+d=0
     //Traverse the last two arrays
     for(int c:nums3){
         for(int d:nums4){
             if(map.containsKey(0-(c+d))){
                 temp += map.get(0-(c+d));//When a+b+c+d=0 is found, record the corresponding times
             }
         }
     }
     return temp;

    }

219. Duplicate Element II exists

• Give you an integer array nums and an integer k, judge whether there are two different indexes I and j in the array, and satisfy nums[i] == nums[j] and ABS (I - J) < = K. If it exists, return true; Otherwise, false is returned.

• analysis:

  • Use sliding window, and the window size shall not be greater than k
  • Traverse the array in turn. When the window length > k, delete the i-k element, which is the first element of the current sliding window
• JAVA

public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set = new HashSet<Integer>();
    for(int i=0;i<nums.length;i++){
        if(set.contains(nums[i])){//There are duplicate elements
            return true;
        }
        set.add(nums[i]);//Add element
        if(set.size()>k){//Number of sliding windows > k
             set.remove(nums[i-k]);//Delete the element, i-k is the current first element
        }
    }
    return false;
    }

character string

151. Flip the words in the string

• Give you a string s and flip all the words in the string one by one.
  A word is a string of non whitespace characters. Use at least one space in s to separate words in the string.
• Please return a string that flips the word order in s and connects it with a single space.
• explain:
  The input string s can contain extra spaces before, after, or between words.
  After flipping, the words should be separated by only one space.
  The flipped string should not contain additional spaces.
• Method 1: use existing methods

public String reverseWords(String s) {
     //Remove white space at the beginning and end
     s = s.trim();
     //Regular matching cuts continuous white space characters as separators
     List<String> wordList = Arrays.asList(s.split("\\s+"));
     Collections.reverse(wordList);
     //Reorganizes the string according to the specified separator
     return String.join(" ",wordList);
    }

• Method 2: use custom methods

//Using custom methods
public String reverseWords_2(String s) {
    StringBuilder sb = trimSpaces(s);

    // Flip string
    reverse(sb, 0, sb.length() - 1);

    // Flip each word
    reverseEachWord(sb);

    return sb.toString();
}

//Remove spaces
public StringBuilder trimSpaces(String s){
    int left = 0,right = s.length()-1;
    // Remove header space
    while(left <= right && s.charAt(left)==' '){
        ++left;//Move the left pointer to the right
    }

    //Remove trailing spaces
    while(left<=right && s.charAt(right)==' '){
        --right;//The right pointer moves to the left
    }

    //Remove extra white space characters
    StringBuilder sb = new StringBuilder();
    while(left <= right){
        char c = s.charAt(left);
        if(c != ' '){
            sb.append(c);
        }else if(sb.charAt(sb.length()-1)!=' '){
            sb.append(c);
        }
        ++left;
    }
    return sb;
}

//reversal
public void reverse(StringBuilder sb,int left,int right){
    while(left < right){
        char temp = sb.charAt(left);
        sb.setCharAt(left++,sb.charAt(right));//Head to tail swap
        sb.setCharAt(right--,temp);
    }
}

//Invert each letter
public void reverseEachWord(StringBuilder sb){
    int n = sb.length();
    int start = 0,end = 0;
    
    while (start < n) {
        // Loop to end of word
        while (end < n && sb.charAt(end) != ' ') {
            ++end;
        }
        // Flip Words 
        reverse(sb, start, end - 1);
        // Update start to find the next word
        start = end + 1;
        ++end;
    }
}

344. String inversion

• Write a function that inverts the input string. The input string is given in the form of character array char [].
• Do not allocate additional space to another array. You must modify the input array in place and use the additional space of O(1) to solve this problem.
• You can assume that all characters in the array are printable characters in the ASCII code table.

public void reverseString(char[] s) {
    for(int i=0,j=s.length-1;i<j;i++,j--){
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }
    System.out.println(s);
}

541. String inversion II

• Given a string s and an integer k, you need to reverse the first k characters of every 2k characters from the beginning of the string.

  • If there are less than k remaining characters, all remaining characters are reversed.
  • If the remaining characters are less than 2k but greater than or equal to K, the first k characters are reversed and the remaining characters remain the same.
• Example:
  Input: s = "abcdefg", k = 2
  Output: "bacdfeg"

• analysis:

  • i is traversed by the growth rate of i+=(2*k)
  • Judge two situations

  public String reverseStr(String s, int k) {
  for(int i=0;i<s.length();i+=(2*k)){
      //1. Invert the first k characters every 2k characters
      //2. If the remaining characters are < 2K but > = k, the first k characters will be reversed
      if(i+k<=s.length()){
          s = reverse(s,i,i+k-1);
          continue;
      }
      //3. If the remaining characters are < K, all the remaining characters will be reversed
      s = reverse(s,i,s.length()-1);
  
  }
  return s;
  
  }
  //Reverses characters with subscripts a through b
  public String reverse(String s,int start,int end){
  char[] ch = s.toCharArray();
  for(int i = start,j = end;i<j;i++,j--){
      char temp = ch[i];
      ch[i] = ch[j];
      ch[j] = temp;
  }
  
  
  return new String(ch);
  }

  05. Replace blank space (Sword finger offer)

• Please implement a function to replace each space in the string s with "% 20".

• analysis:

  • Create a character array three times the length of string s to ensure that the replaced string can be loaded
  • size is used to calculate the real length of the replaced string
  • i=0 to start traversing the string: when it is judged that there are spaces, it is stored in% 20 in turn; Conversely, normal assignment.

  public String replaceSpace(String s) {
    //Establish a character array to ensure that the replaced capacity can be loaded
    char[] ch = new char[s.length()*3];
    int size = 0;//Calculates the length of the replaced string
    for(int i=0;i<s.length();i++){
        char c = s.charAt(i);
        if(c == ' '){//When it is judged as a space, it is stored in sequence
            ch[size++] = '%';
            ch[size++] = '2';
            ch[size++] = '0';
        }else{//Conversely, normal assignment
            ch[size++] = c;
        }
    }
    //Reinitialize the new string, which is the length after replacement
    String result = new String(ch,0,size);
    return result;
  
    }

58.II left rotation string (Sword finger offer)

• The left rotation operation of a string is to transfer several characters in front of the string to the end of the string. Please define a function to realize the function of string left rotation operation.
• For example, if you enter the string "abcdefg" and the number 2, the function will return the result "cdefgab" obtained by rotating the left two digits.

public String reverseLeftWords(String s, int n) {

    int len = s.length();
    char[] arr = new char[s.length()];
    //Characters before subscript k of assignment
    for(int i=s.length()-n;i<len;i++){
        arr[i] = s.charAt(i-len+n);
    }
    //The assignment subscript is k and the characters after k
    for(int i=n;i<len;i++){
        arr[i-n] = s.charAt(i);
    }
    
    String result = new String(arr,0,len);
    return result;

    }

28. Implement str ()

• Implement the strStr() function. Here are two strings: haystack and need. Please find the first position of the need string in the haystack string (the subscript starts from 0). If it does not exist, - 1 is returned.

• JAVA

  public int strStr(String haystack, String needle) {
    if(needle==null){
        return -1;
    }
    int i=0,j = 0,k=0;
    while(i<haystack.length() && j<needle.length()){
        if(haystack.charAt(i) == needle.charAt(j)){
            i++;
            j++;
        }else{
            j=0;
            i = ++k;
        }
    }
    if(j>=needle.length()){
        return k;
    }else{
        return -1;
    }
    }

Stack and queue

232. Implement queue with stack

• Please use only two stacks to implement the first in first out queue. The queue should support all operations supported by the general queue (push, pop, peek, empty):

• Implement MyQueue class:

  • void push(int x) pushes element X to the end of the queue
  • int pop() removes the element from the beginning of the queue and returns it
  • int peek() returns the element at the beginning of the queue
  • boolean empty() returns true if the queue is empty; Otherwise, false is returned

• analysis:

  • The queue is implemented with two stacks: an input stack and an output stack
  • First import the elements into the input stack, for example: 1 2 3 after import, it is (top of stack) ← 3 2 1 ← (bottom of stack)
  • Then import the elements into the output stack, for example: ← 3 2 1 ← after import, it will be (top of stack) ← 1 2 3 ← (bottom of stack)
  • Pop from the output stack has: 1 2 3, so as to realize first in first out

  public class MyQueue {
  
    Stack<Integer> stIn;//Stack for input elements
    Stack<Integer> stOut;//Stack for output elements
  
    //initialization
    public MyQueue() {
        stIn = new Stack<Integer>();
        stOut = new Stack<Integer>();
    }
  
    //Simulated team entry
    public void push(int x) {
        stIn.push(x);//Enter the stack
    }
  
    //Simulated team
    public int pop() {
        // Only when the output stack of STUT is empty can the elements in stIn be input
        if(stOut.empty()){
            while(!stIn.empty()){
                stOut.push(stIn.pop());
            }
        }
        return stOut.pop();//Returns the top element of the stack and deletes it
    }
  
    //Return queue header element
    public int peek() {
        //Same as simulated team out
        if(stOut.empty()){
            while(!stIn.empty()){
                stOut.push(stIn.pop());
            }
        }
        return stOut.peek();//Returns the top element of the stack, but does not delete it
    }
  
    //Judge whether the queue is empty
    public boolean empty() {
        //When both stacks are empty, the queue is empty
        return stIn.empty() && stOut.empty();
    }
  }

  225. Implement stack with queue

• Please use only two queues to implement a last in first out (LIFO) stack, and support all four operations of the ordinary stack (push, top, pop and empty).

• Implement MyStack class:

  • void push(int x) pushes element X to the top of the stack.
  • int pop() removes and returns the top of stack element.
  • int top() returns the top element of the stack.
  • boolean empty() returns true if the stack is empty; Otherwise, false is returned.

• analysis:

  • Use a queue and join the queue normally first
  • Then insert the queue, starting from the queue head element, into the tail of the queue
  • The queue can be inverted to form a first in and last out rule

//252. Implement stack with queue
public class MyStack {
    Deque<Integer> dq;
    
    /** Initialize your data structure here. */
    public MyStack() {
        dq = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        int size = dq.size();
        dq.offer(x);//Insert tail
        for(int i=0;i<size;i++){
            dq.offer(dq.poll());//poll returns the first entry element, that is, the header element
            //Insert this element at the end of the queue
            //This method is to invert the original queue, which has formed the principle of first in and last out
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return dq.poll();//Return queue header element
    
    }
    
    /** Get the top element. */
    public int top() {
        return dq.peek();//Returns the first element, the current queue head element
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return dq.isEmpty();
    }
}

20. Valid brackets

• Given a string s that only includes' (',' ',' {','} ',' [','] ', judge whether the string is valid.

• Valid strings must meet:

  1. The left parenthesis must be closed with the same type of right parenthesis.
  2. The left parentheses must be closed in the correct order.

• analysis:

  • Three mismatches

    1. The left bracket is redundant

        ~~(~~  [ { } ] ( )

    2. There are no extra brackets, but the bracket type does not match

        ( ~~[~~  { } ~~}~~  )

    3. The right bracket is redundant

        ( [ { } ] ) ~~)~~  ~~)~~ 

  • Three judgment methods

    1. The first case: the traversal has been completed, but the stack is not empty, it indicates that there are redundant right parentheses
    2. In the second case, when the closing bracket is matched, no matching character is found in the stack
    3. In the third case, if the stack is empty but the string s is not traversed, it indicates that there are redundant left parentheses

• Java

  public boolean isValid(String s) {
    Stack<Character> st = new Stack<Character>();
    for(int i=0;i<s.length();i++){
        //Here, the right bracket of the stack is convenient to directly match whether there is the same bracket in the string s
        if(s.charAt(i)=='(') st.push(')');
        else if(s.charAt(i)=='{') st.push('}');
        else if(s.charAt(i)=='[') st.push(']');
        //In the third case, if the stack is empty but the string s is not traversed, it indicates that there are redundant left parentheses
        //In the second case, when the closing bracket is matched, no matching character is found in the stack
        else if(st.empty() || st.peek()!=s.charAt(i)) {
            return false;
        }
        /*
        Implicit judgment success:
        s.charAt(i)=='(' or 
        s.charAt(i)=='{' or 
        s.charAt(i)=='['
        */
        else st.pop();
  
  }
    //The first case: the traversal has been completed, but the stack is not empty, it indicates that there are redundant right parentheses
    return st.empty();
  }

  1047. Delete all adjacent duplicates in the string

• Given the string S composed of lowercase letters, the duplicate deletion operation will select two adjacent and identical letters and delete them.
• Repeat the duplicate deletion operation on S until the deletion cannot continue.
• Returns the final string after all deduplication operations are completed. The answer is guaranteed to be unique.

• analysis:

  • Define a stack. When it is judged that the top element of the stack is the same as the traversed element, it will be out of the stack
  • Finally, reverse it

  public String removeDuplicates(String s){
    Stack<Character> st = new Stack<Character>();
        for(int i=0;i<s.length();i++){
            if(!st.isEmpty()){
                //Judge whether there are adjacent elements
                if(st.peek()==s.charAt(i)){
                    st.pop();
                    continue;
                }
            }
        
            st.push(s.charAt(i));//Push 
        
        }
        //If there is no element in the stack, null is returned
        if(st.isEmpty()){
            return "";
        }
        char[] ch = new char[st.size()];
        //reversal
        for(int i=ch.length-1;i>=0;i--){//Note: the length of the stack cannot be used, because it will change every time it comes out of the stack
            ch[i] = st.pop();
        }
        //Remake string
        String result = new String(ch, 0, ch.length);
        
        return result;
  }

150. Evaluation of inverse Polish expression

• Find the value of the expression according to the inverse Polish representation.
• Valid operators include +, -, *, /. Each operand can be an integer or another inverse Polish expression.

• explain:

  • Integer division preserves only the integer part.
  • The given inverse Polish expression is always valid. In other words, an expression always yields a valid value and there is no case where the divisor is 0.

• analysis:

  1. Reverse Polish is the suffix. Change the suffix to infix

  2. Stack numbers in sequence:

     1. When arithmetic symbols appear, two numbers are stacked
     2. Exchange the order of two numbers (ensure the correct order)
     3. Operate two numbers with the symbol and put the result on the stack

public int evalRPN(String[] tokens) {
    Deque<Integer> dq = new LinkedList<Integer>();
    for(int i=0;i<tokens.length;i++){
        //Judge whether it is arithmetic symbol
        if(tokens[i].equals("+")||tokens[i].equals("-")
        ||tokens[i].equals("*")||tokens[i].equals("/")){
            int a = dq.pop();
            int b = dq.pop();
            switch (tokens[i]){
                case "+":
                    dq.push(b+a);
                    break;
                case "-":
                    dq.push(b-a);
                    break;
                case "*":
                    dq.push(b*a);
                    break;
                case "/":
                    dq.push(b/a);
                    break;
                default:
            }
        }else{
            dq.push(Integer.parseInt(tokens[i]));//Convert string to number
        }
    }
    return dq.peek();
}

Binary tree

Recursive explanation

• Recursive three elements

  1. Determine the parameters and return value of recursive function: that is, determine the parameters in recursion and specify the return value of each recursion.
  2. Determine the termination condition: that is, ensure that there is no stack overflow.
  3. Determine the logic of single-layer recursion: determine the information to be processed by each layer of recursion.

  144. Preorder traversal of binary tree

• analysis:

  • Preorder traversal, also known as first root, traverses a binary tree in the order of root, left and right

• C (recursive)

  void preorder(TreeNode *root,int *res,int *resSize) {
    if (root != NULL) {
        //Storing values in an array
        res[(*resSize)++] = root->val;//Array self increment
        preorder(root->left, res, resSize);
        preorder(root->right, res, resSize);
    }
    
    
  }
  int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int *res = malloc(sizeof(int) * 2000);
    *returnSize = 0;
    preorder(root, res, returnSize);
    return res;
  }

• C (non recursive)

  int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int *result = (int*)malloc(sizeof(int) * 2000);//Generate a result array
    *returnSize = 0;
    if (root == NULL) {
        return result;
    }
    struct TreeNode *st[2000];//Define a stack
    struct TreeNode *p = root;//Define a pointer
    int top = -1;//Initialization stack
    st[++top] = root;//Stack root node
    while (top != -1) {
        p = st[top--];//The pointer points to the current node to be traversed (around the root)
        result[(*returnSize)++] = p->val;//Input result array
        if (p->right != NULL) {//Right child exists
            st[++top] = p->right;
        }
        if (p->left != NULL) {//Left child exists
            st[++top] = p->left;
        }
    }
    return result;
  }

94. Middle order traversal of binary tree

• C (recursive)

  void inorder(struct TreeNode* root, int *res, int *resSize) {
    if (root == NULL) {
        return;
    }
    inorder(root->left, res, resSize);
    res[(*resSize)++] = root->val;
    inorder(root->right, res, resSize);
  }
  int *inorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = (int*)malloc(sizeof(int) * 2000);
    *returnSize = 0;
    inorder(root, res, returnSize);
    return res;
  }

• C (non recursive)

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int *result = (int*)malloc(sizeof(int) * 2000);//Generate a result array
    *returnSize = 0;
    if (root == NULL) {
        return result;
    }
    struct TreeNode *st[2000];//Define a stack
    struct TreeNode *p;//Define a pointer
    int top = -1;//Pointer to initialization stack
    p = root;//p points to the root node
    while (top != -1 || p != NULL) {//It is possible that the stack is empty but the tree is not traversed
        while (p != NULL) {//The left child has been in the stack
            st[++top] = p;
            p = p->left;
        }
        if (top != -1) {//Output when stack is not empty
            p = st[top--];
            result[(*returnSize)++] = p->val;
            p = p->right;
        }
    }
    return result;
}

145. Post order traversal of binary tree

• C

void postorder(TreeNode *root, int *res, int *resSize) {
    if (root == NULL) {
        return;
    }
    postorder(root->left, res, resSize);
    postorder(root->right, res, resSize);
    res[(*resSize)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int *res = (int*)malloc(sizeof(int) * 2000);
    *returnSize = 0;
    postorder(root, res, returnSize);
    return res;
}

• C (iteration)

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int *result = (int*)malloc(sizeof(int) * 2000);//Result array
    *returnSize = 0;
    if (root = NULL) {
        return result;
    }
    struct TreeNode *stack1[2000]; int top1 =  1;
    struct TreeNode *stack2[2000]; int top2 = -1;
    struct TreeNode *p = NULL;
    stack1[++top1] = root;//Root node stack
    while (top1 != -1) {
        p = stack1[top1--];//point
        stack2[++top2] = p;//reentry
        if (p->left != NULL) {//Reverse stack
            stack1[++top1] = p->right;
        }
            
        if (p->right != NULL) {
            stack1[++top1] = p->left;
        }
        
    }
    while (top2 != -1) {
        //The next step is post order traversal
        p = stack2[top2--];
        result[(*returnSize)++] = p->val;
    }
    return result;

}

226. Flip binary tree

• Give you the root node of a binary tree. Flip the binary tree and return to its root node.

• Method 1:

  • Define a node as an intermediate variable
  • Recursively exchange the left and right subtrees in turn, and end when it is empty
• JAVA

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

• Method II

  • Define two nodes, left and right
  • Recursive traversal, let left point to the right subtree of the tree and right point to the left subtree of the tree
  • Then let the original root node point to left and right
• JAVA

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