Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 145. Binary Tree Postorder Traversal

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 1:

Solution 2:

Solution 3:

 

花花酱 LeetCode 154. Find Minimum in Rotated Sorted Array II

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:

花花酱 LeetCode 637. Average of Levels in Binary Tree

 

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:

花花酱 Leetcode 153. Find Minimum in Rotated Sorted Array

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:

 

花花酱 LeetCode 79. Word Search

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:

C++



Python