111. Minimum Depth of Binary Tree

As we all know how to find the Max depth of the tree.Here we can review the thoughts at the time,

1. If the root is null,so the max depth is 0
2. count the left subtree depth
3. count the right subtree depth
4. max depth of the current tree = the greater of the max depth of the left subtree and the max depth of the right subtree

If we find the min depth,what to keep and what to modify?

1. If the root is null,so the max depth is 0
2. If the left and right subtree are all null,so the depth is 1
3. count the left subtree depth

4. count the right subtree depth

   • but we can't get the max depth,we get the smaller of them
   • we can preset the number of layers to the maximum
5. the min subtree's depth plus this layer depth 1

solution

  public int minDepth(TreeNode root) {
    return findMin(root);
  }

  private int findMin(TreeNode node) {
    //let the number of this layer be the largest
    int depth = Integer.MAX_VALUE;
    //if this layer is null,so it doesn't have subtree
    if (node == null) {
      return 0;
    }
    //if just have the node tree,so the number of the layer is 1
    if (node.left == null && node.right == null) {
      return 1;
    }
    //get the min number of the subtree
    if (node.left != null) {
      depth = Math.min(findMin(node.left), depth);
    }
    if (node.right != null) {
      depth = Math.min(findMin(node.right), depth);
    }
    //plus this node tree layer number 1
    return depth + 1;
  }

112. Path Sum

This problem is a very typical recursion problem.I think it is very similar to the Tower of Hanoi problem.

Let's take a closer look at this photo

1. if 11 don't have a left subtree and right subtree,it is a leaf
2. the target number is 22,but we minus the right subtree is 22
3. this question change can we start 7 to the root-to-leaf,plus the all number can be 22?
4. after constant recursion
5. this question change 4 left subtree can plus 5 22?or 8 right subtree plus 5 get 22

So this question we can get the recursion thought

1. if the node is null,return false
2. if the left subtree and the right subtree are all null,so judge this node value whether equals to the target sum
3. judge the left subtree number and right subtree number whether equals to the target sum minus the node value

solution

  public boolean hasPathSum(TreeNode root, int targetSum) {
    //if don't have this node,just return false
    if (root == null) {
      return false;
    }
    //judge this node value whether equals to the target number
    if (root.left == null && root.right == null) {
      return targetSum == root.val;
    }
    //recursion this function,find target number minus this node value
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right,
        targetSum - root.val);
  }

118. Pascal's Triangle

This question is a very easy question.Like a two-dimensional array,but this is a List question.

1. head and tail number must be 1
2. $j<=i$
3. [i][j]=[i-1][j-1]+[i-1][j]

So we can solve this problem easily

solution

  public List<List<Integer>> generate(int numRows) {
    ArrayList<List<Integer>> lists = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
      ArrayList<Integer> arrayList = new ArrayList<Integer>();
      for (int j = 0; j <= i; j++) {
        //the head and tail must be 1
        if (j == 0 || j == i) {
          arrayList.add(1);
        } else {
          //[i-1][j-1]+[i-1][J]
          arrayList.add(lists.get(i - 1).get(j - 1) + lists.get(i - 1).get(j));
        }
      }
      //add this new lists
      lists.add(arrayList);
    }
    return lists;
  }

119. Pascal's Triangle II

This problem is very similar to number118.If you understand number118,then you can solve this problem easily.

solution

  public List<Integer> getRow(int rowIndex) {
    ArrayList<List<Integer>> lists = new ArrayList<>();
    //this question example rowIndex = 3,[1,3,3,1].So the answer is the line 4,we should plus
    for (int i = 0; i < rowIndex + 1; i++) {
      ArrayList<Integer> arrayList = new ArrayList<>();
      for (int j = 0; j <= i; j++) {
        if (j == 0 || j == i) {
          arrayList.add(1);
        } else {
          arrayList.add(lists.get(i - 1).get(j - 1) + lists.get(i - 1).get(j));
        }
      }
      lists.add(arrayList);
    }
    //get the answer
    return lists.get(rowIndex);
  }

121. Best Time to Buy and Sell Stock

This problem is also a Dynamic programming problem.The time complexity of this kind of problem is generally $O(n)$. This problem has two solutions,one solution is Brute force calculation.But this solution can be out of time.

solution1

  public int maxProfit(int[] prices) {
    int result = 0;
    //beginning for the head
    for (int i = 0; i < prices.length - 1; i++) {
      for (int j = i + 1; j < prices.length; j++) {
        //compare i ,i+1,until the end
        if (prices[i] < prices[j]) {
          if (result < prices[j] - prices[i]) {
            //update the result
            result = prices[j] - prices[i];
          }
        }
      }
    }
    return result;
  }

The second solution is a very easy thinking.This problem is to find the max price.So we must find the min price to buy.And find the max price which after the min price.

solution2

  public int maxProfit(int[] prices) {
    int maxPrice = Integer.MAX_VALUE;
    int result = 0;
    for (int i = 0; i < prices.length; i++) {
      //find the min price
      if (prices[i] < maxPrice) {
        maxPrice = prices[i];
      } else if (result < prices[i] - maxPrice) {
        //find the max price which after the min price
        result = prices[i] - maxPrice;
      }
    }
    return result;
  }

125. Valid Palindrome

This problem is a not difficult but very complicated to solve.We can use double pointers to solve it.

1. if head is not lowercase and uppercase letter and is not a number,just plus
2. if tail is not lowercase and uppercase letter and is not a number,just minus
3. use the ASCII to judge the head,if the lowercase or the number,we don't need to
   change,if the uppercase,just change to the lowercase
4. use the ASCII to judge the tail,if the lowercase or the number,we don't need to
   change,if the uppercase,just change to the lowercase
5. judge the head and the tail
6. the end is head>=tail

So this problem has many judgement,it will make a lot of time to write,it is very complicated

solution

  public boolean isPalindrome(String s) {
    //make double pointers
    int head = 0, tail = s.length() - 1;
    while (head <= tail) {
      //if head is not lowercase and uppercase letter and is not a number,just plus
      while (head <= tail && !(s.charAt(head) >= 'a' && s.charAt(head) <= 'z') && !(
          s.charAt(head) >= 'A' && s.charAt(head) <= 'Z') && !(s.charAt(head) >= '0'
          && s.charAt(head) <= '9')) {
        head++;
      }
      //if tail is not lowercase and uppercase letter and is not a number,just minus
      while (head <= tail && !(s.charAt(tail) >= 'a' && s.charAt(tail) <= 'z') && !(
          s.charAt(tail) >= 'A' && s.charAt(tail) <= 'Z') && !(s.charAt(tail) >= '0'
          && s.charAt(tail) <= '9')) {
        tail--;
      }
      //make two temps
      char headTemp, tailTemp;
      //if the s is null character.such as "  ".it will out of time,so this is to judge the s
      if (head > tail) {
        return true;
      }
      //we can use the ASCII to judge the head,if the lowercase or the number,we don't need to
      // change
      if ((s.charAt(head) >= 'a' && s.charAt(head) <= 'z') || (s.charAt(head) >= '0'
          && s.charAt(head) <= '9')) {
        headTemp = s.charAt(head);
      } else {
        //if the uppercase,just change to the lowercase
        headTemp = (char) ((int) s.charAt(head) + 32);
      }
      //we can use the ASCII to judge the tail,if the lowercase or the number,we don't need to
      // change
      if ((s.charAt(tail) >= 'a' && s.charAt(tail) <= 'z') || (s.charAt(tail) >= '0'
          && s.charAt(tail) <= '9')) {
        tailTemp = s.charAt(tail);
      } else {
        //if the uppercase,just change to the lowercase
        tailTemp = (char) ((int) s.charAt(tail) + 32);
      }
      //just judge the head and the tail
      if (headTemp == tailTemp) {
        head++;
        tail--;
        continue;
      } else {
        return false;
      }
    }
    return true;
  }

136. Single Number

Java Xor Operator is a very elegant method,it's not like a HashMap.It doesn't cost a lot of space.

1. Any number and 0 are XOR,the result is still the original number,a^0=a
2. XOR any number with itself,the result is 0,a^a=0
3. The exclusive XOR operation satisfies the commutative law and associative law.a^b^a=b^a^a=b^(a^a)=b^0=b

solution

  public int singleNumber(int[] nums) {
    int number = 0;
    for (int num : nums) {
      number ^= num;
    }
    return number;
  }

141. Linked List Cycle

This is a typical problem of fast and slow pointers.I wrote a note about double pointers in my Blog Data Structure Chapter6 If you want to know about it,you can read it.

solution

  public boolean hasCycle(ListNode head) {
    //make fast and slow double pointer
    ListNode fast = head, slow = head;
    //test example [] -1,just return false
    if (fast == null) {
      return false;
    }
    while (fast.next != null && fast.next.next != null) {
      fast = fast.next.next;
      slow = slow.next;
      //has cycle
      if (fast == slow) {
        return true;
      }
    }
    return false;
  }

144. Binary Tree Preorder Traversal

This is a very simple Binary Tree problem.I wrote typical note in my blog Data Structure Chapter11 If you want to know more about Binary Tree,you can read it.

solution

  public List<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> list = new ArrayList<>();
    preErgodic(root, list);
    return list;
  }

  private void preErgodic(TreeNode node, ArrayList<Integer> keys) {
    //if the node is null,just return
    if (node == null) {
      return;
    }
    //add the ArrayList
    keys.add(node.val);
    //the left subtree
    if (node.left != null) {
      preErgodic(node.left, keys);
    }
    //the right subtree
    if (node.right != null) {
      preErgodic(node.right, keys);
    }
  }

145. Binary Tree Postorder Traversal

This is a very simple Binary Tree problem.I wrote typical note in my blog Data Structure Chapter11 If you want to know more about Binary Tree,you can read it.

solution

  public List<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> list = new ArrayList<>();
    afterErgodic(root, list);
    return list;
  }

  private void afterErgodic(TreeNode node, ArrayList<Integer> keys) {
    if (node == null) {
      return;
    }
    if (node.left != null) {
      afterErgodic(node.left, keys);
    }
    if (node.right != null) {
      afterErgodic(node.right, keys);
    }
    keys.add(node.val);
  }