Problem

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

For example, given

1
2

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

1
2
3
4
5

    3
   / \
  9  20
    /  \
   15   7

Problem

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

For example, given

1
2

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

1
2
3
4
5

    3
   / \
  9  20
    /  \
   15   7

Problem

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],

Problem

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

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

1
2
3
4
5

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

1
2
3
4
5

[
  [3],
  [20,9],
  [15,7]
]

Problem

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

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

1
2
3
4
5

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

1
2
3
4
5

[
  [3],
  [9,20],
  [15,7]
]

Problem

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

Note: Bonus points if you could solve it both recursively and iteratively.

Problem

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

Problem

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

• A solution using O(n) space is pretty straight forward.
• Could you devise a constant space solution?

Problem

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees.

Example 1:

1
2
3
4
5
6

    2
   / \
  1   3

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

Example 2:

1
2
3
4
5
6
7
8
9

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Problem

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

1
2

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

1
2

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false