Haiyang Yu's Blog

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

1
2

Input: [2,2,1]
Output: 1

Example 2:

1
2

Input: [4,1,2,1,2]
Output: 4

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

return its depth = 3.

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

1
2

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

1
2

Input: strs = [""]
Output: [[""]]

Example 3:

1
2

Input: strs = ["a"]
Output: [["a"]]

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lower-case English letters.

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

1
2

Input: [1,2,0]
Output: 3

Example 2:

1
2

Input: [3,4,-1,1]
Output: 2

Example 3:

1
2

Input: [7,8,9,11,12]
Output: 1

Follow up:

Your algorithm should run in O(n) time and uses constant extra space.

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

Example 1:

1
2

Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:

1
2

Input: root = []
Output: []

Example 3:

1
2

Input: root = [1]
Output: [1]

Example 4:

1
2

Input: root = [1,2]
Output: [2,1]

Example 5:

1
2

Input: root = [1,null,2]
Output: [2,1]

Constraints:

• The number of the nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Follow up:

Recursive solution is trivial, could you do it iteratively?

Given the root of a binary tree, return the preorder traversal of its nodes’ values.

Example 1:

1
2

Input: root = [1,null,2,3]
Output: [1,2,3]

Example 2:

1
2

Input: root = []
Output: []

Example 3:

1
2

Input: root = [1]
Output: [1]

Example 4:

1
2

Input: root = [1,2]
Output: [1,2]

Example 5:

1
2

Input: root = [1,null,2]
Output: [1,2]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Follow up:

Recursive solution is trivial, could you do it iteratively?

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Example 1:

1
2

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

1
2

Input: root = []
Output: []

Example 3:

1
2

Input: root = [1]
Output: [1]

Example 4:

1
2

Input: root = [1,2]
Output: [2,1]

Example 5:

1
2

Input: root = [1,null,2]
Output: [1,2]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Follow up:

Recursive solution is trivial, could you do it iteratively?

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
2
3
4
5

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1
2
3
4
5

  1
 / \
2   2
 \   \
 3    3

Follow up: Solve it both recursively and iteratively.

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

1
2
3
4
5
6
7

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

1
2
3
4
5
6
7

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

1
2
3
4
5
6
7

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

1
2
3

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

1
2
3

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"