# Problem:

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

For example:
Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

# Solution 3:

Problem:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Idea:

Divide and conquer

Time complexity:

Average: O(logn)

Worst: O(n)

Solution:

Related Problems:

Problem:

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

Time Complexity:

O(n)

Space Complexity:

O(h)

Solution 1:

BFS

Solution 2:

DFS

Related Problems:

Problem:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Idea:

Divide and conquer.

Evenly Split the array into two sub-arrays, and find the minimums of them, return the smaller one.

findMin(a[0..n]) = min(findMin(a[0..n/2], a[n/2..n])

Key property:

One of the sub-array will be a sorted array, it takes O(1) to find the minimal element, just the first element.

Time complexity:

T(n) = O(1) + T(n/2) = O(logn)

Solution:

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Idea:
Search, depth first search
Solution: