# 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
}
//compare each node
} else {
}
}
}

# 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];
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
//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
//add the left node and right node
//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)
}
//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

  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.