70. Climbing Stairs

This problem it seem just like Tower of Hanoi,so we can use the same idea to solve this problem

• $1 stair:1=1+0$​​​
• $2stairs: 2=1+1=2$
• $3stairs:1stair+2stairs=3=1+1+1=1+2=2+1$
• $4stairs:3stairs+2stairs=5=2+2=1+1+1+1=2+1+1=1+2+1=1+1+2$

solution

  public int climbStairs(int n) {
    //p is stair0,q is stair1,result is sum of two stairs
    int p = 0, q = 1, result = 0;
    //result is 1,2,3,4...
    for (int i = 0; i < n; i++) {
      result = p + q;
      p = q;
      q = result;
    }
    return result;
  }

83. Remove Duplicates from Sorted List

This problem is a easy Singly linked list problem.If you want to learn more about Singly linked list,you can read more in my blog Data Structure Chapter5.

solution

  public ListNode deleteDuplicates(ListNode head) {
    //if ListNode is [],just return
    if (head == null) {
      return head;
    }
    //marked the old head
    ListNode oldHead = head;
    //form head to tail
    while (head.next != null) {
      //compare each node 
      if (head.val == head.next.val) {
        head.next = head.next.next;
      } else {
        head = head.next;
      }
    }
    //return the head
    return oldHead;
  }

88. Merge Sorted Array

This problem is a very easy problem.We can use double pointer solve this problem easily.

solution

  public void merge(int[] nums1, int m, int[] nums2, int n) {
    //make a new array to get the answer
    int[] result = new int[m + n];
    //beginning from both head
    int i = 0, j = 0, temp;
    while (i < m || j < n) {
      if (i == m) {
        //if nums1 is ending just copy the nums2
        temp = nums2[j++];
      } else if (j == n) {
        //if nums2 is ending just copy the nums1
        temp = nums1[i++];
      } else if (nums1[i] < nums2[j]) {
        //copy the smaller number
        temp = nums1[i++];
      } else {
        temp = nums2[j++];
      }
      result[i + j - 1] = temp;
    }
    //copy the answer to the nums1
    for (int length = 0; length < n + m; length++) {
      nums1[length] = result[length];
    }
  }

94. Binary Tree Inorder Traversal

Use recursion to solve this problem.This problem is a very symble in Binary Tree.I wrote a very detailed note about Binary Tree Data Structure Chapter11.You can read it and clear how to Inorder traversal.And Inorder, Preorder and Postorder

solution

  public List<Integer> inorderTraversal(TreeNode root) {
    //make an array to store the notes
    ArrayList<Integer> array = new ArrayList<>();
    //use the method
    midErgodic(root, array);
    //return the array
    return array;
  }

  public void midErgodic(TreeNode root, List<Integer> array) {
    //this root is not exist
    if (root == null) {
      return;
    }
    //recursion the left note
    if (root.left != null) {
      midErgodic(root.left, array);
    }
    //add this root into the arrays
    array.add(root.val);
    //recursion the right root
    if (root.right != null) {
      midErgodic(root.right, array);
    }
  }

100. Same Tree

This problem is a sequence traversal of binary tree.I wrote the detailed ideads in my notes Data Structure Chapter11.The main idea is search from the root,and search left and right.But you must be attention is if the location is null,you must compare with the another tree the same location too.If you use the ArrayList to store data,you must store the null not only the numbers,

Because the [1,2]is not the same[1,null,2].So i can use the recursive to solve this problem too.

There's one thing we must be atention.

right solution

else if (p.val != q.val) {
     return false;
} else {
     return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

failed solution

else if (p.val == q.val) {
     return true;
} else {
     return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

If the same location is equal.We must judge the left and right tree,If we use the failed solution.Such as [1,2]and[1,null,2],we can't judge the subtree.

solution

  public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
      //if the same location is null,then this location is true
      return true;
    } else if (p == null || q == null) {
      //if one is null,the another one is not null,return false
      return false;
    } else if (p.val != q.val) {
      //we can't use p.val==q.val return true.If will judgement after interruption
      return false;
    } else {
      //recursive the same location
      return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
  }

101. Symmetric Tree

This problem has two solutions,but the main idea is the same.

I make some examples

• A B B A true
• A null false
• A null null A false
• The tree only have a root is true

So I can use recursively and iteratively to solve this problem.

recursion

Termination condition

• left is not equal to right,or left and right are both null

recursive comparison each tree,both two tree roots are the same.and left.left equals to right.right,left.right equals to right.left

solution1

  public boolean isSymmetric(TreeNode root) {
    //the root is not to judge,we judge the subtree
    return symmetric(root.left, root.right);
  }

  public boolean symmetric(TreeNode p, TreeNode q) {
    //null null is the symmetric
    if (p == null && q == null) {
      return true;
    } else if (p == null || q == null) {
      //null number or number null is not symmetric
      return false;
    } else {
      //val is equal and the left subtree and right subtree is symmetric,it is true
      return p.val == q.val && symmetric(p.left, q.right) && symmetric(p.right, q.left);
    }
  }

iteration

We can make a Queue to store the note.Just like Push and Pop.The conparison method is similar to recursion.roots are the same,left.left==right.right,left.right==right.left.Until the Queue is empty,it means the tree is symmetric

solution2

  public boolean isSymmetric(TreeNode root) {
    //if root is null or only have the root
    if (root == null || (root.left == null && root.right == null)) {
      return true;
    }
    //make a LinkedList to store the notes
    LinkedList<TreeNode> Queue = new LinkedList<>();
    //add the left node and right node
    Queue.add(root.left);
    Queue.add(root.right);
    //iterate through the loop
    while (Queue.size() > 0) {
      //pop the first node
      TreeNode leftNode = Queue.removeFirst();
      //pop the second node
      TreeNode rightNode = Queue.removeFirst();
      //if left is null and right is null
      if (leftNode == null && rightNode == null) {
        continue;
      } else if (leftNode == null || rightNode == null) {
        //left is number and right is null or right is number and left is null
        return false;
      } else if (leftNode.val != rightNode.val) {
        //values are not equal
        return false;
      }
      //make a example A(1) B(1) B(2) A(2)
      //add A(1)
      Queue.add(leftNode.left);
      //add A(2)
      Queue.add(rightNode.right);
      //add B(1)
      Queue.add(leftNode.right);
      //add B(2)
      Queue.add(rightNode.left);
    }
    //if the Queue is empty,so it is true
    return true;
  }

104. Maximum Depth of Binary Tree

This problem is a vary easy problem.If we have a clear thinking it is easy to solve it.

Implementation steps

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

solution

  public int maxDepth(TreeNode root) {
    return maxDepthSolution(root);
  }

  private int maxDepthSolution(TreeNode x) {
    //if node is null,so the depth is 0
    if (x == null) {
      return 0;
    }
    //define two variables,x.left tree's depth,x.right tree's depth
    int maxL = 0, maxR = 0;
    //count the depth
    if (x.left != null) {
      maxL = maxDepthSolution(x.left);
    }
    if (x.right != null) {
      maxR = maxDepthSolution(x.right);
    }
    //compare the two depth,return the max and plus 1
    return maxL > maxR ? maxL + 1 : maxR + 1;
  }

108. Convert Sorted Array to Binary Search Tree

This problem is a In-order traversal problem.Becasue the characteristic of in-order traversal is orderly.

The alphabetical order is in order.Just like the nums.You can find that the mid number is the subtree's root.The reminds me of binary search.We always find the mid number.

1. if we choose the mid left number as the root,it means the small number as the right subtree.
2. if we choose the mid right number as the root,it means the big number as the right subtree.

solution1

  public TreeNode sortedArrayToBST(int[] nums) {
    return put(nums, 0, nums.length - 1);
  }

  private TreeNode put(int[] nums, int left, int right) {
    //find the mid
    if (left > right) {
      return null;
    }
    //always choose the number to the left of the middle position as the root node
    int mid = (left + right) / 2;
    //make the node tree
    TreeNode treeNode = new TreeNode(nums[mid]);
    //recursive call the put function
    treeNode.left = put(nums, left, mid - 1);
    treeNode.right = put(nums, mid + 1, right);
    return treeNode;
  }

solution2

  public TreeNode sortedArrayToBST(int[] nums) {
    return put(nums, 0, nums.length - 1);
  }

  private TreeNode put(int[] nums, int left, int right) {
    if (left > right) {
      return null;
    }
    int mid = (left + right + 1) / 2;
    TreeNode treeNode = new TreeNode(nums[mid]);
    treeNode.left = put(nums, left, mid - 1);
    treeNode.right = put(nums, mid + 1, right);
    return treeNode;
  }

110. Balanced Binary Tree

This problem is the Problem104 Tree Depth Upgraded version.If you want to understand this problem,you must undertand Problem104.You can read my blog LeetCode EasyTopic Notes3 and Data Structure Chapter11.

Let's analyze this problem.

1. We must to find whether each layer is balanced
2. If the number of layers differs by more than 1,the tree is not balanced
3. We can find from the beginning and compare each layer from the beginning
4. We can also start form the back

Solution1 beginning from the head

  public boolean isBalanced(TreeNode root) {
    //if the root is null,just return null
    if (root == null) {
      return true;
    } else {
      //if the number of layers differs by more than 1 or the left subtree is not balanced or the
      // right subtree is not balanced just return false
      return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left)
          && isBalanced(root.right);
    }
  }

  public int height(TreeNode node) {
    //get each layer subtree max height
    if (node == null) {
      return 0;
    } else {
      return Math.max(height(node.left), height(node.right)) + 1;
    }
  }

This solution cost lot of time,because we should start from the root and we did two recursion.So this solution time is $O(n^2)$,space is $O(n)$

Solution2 beginning form the tail

  public boolean isBalanced(TreeNode root) {
    //if the number of layers differs by more than 1 just return false
    return maxDepth(root) >= 0;
  }

  private int maxDepth(TreeNode x) {
    if (x == null) {
      return 0;
    }
    //verify the left subtree whether balance
    int maxL = maxDepth(x.left);
    //verify the right subtree whether balance
    int maxR = maxDepth(x.right);
    //if one layers is -1,just all return -1
    if (maxL == -1 || maxR == -1 || Math.abs(maxL - maxR) > 1) {
      return -1;
    }
    //get the max depth
    return maxL > maxR ? maxL + 1 : maxR + 1;
  }

This solution we just use one recursion,so the time cost just only $O(n)$ and the space is $O(n)$ too.