Layer-by-layer traversal is a breadth-first algorithm

Breadth-first search is a traversal search algorithm widely used in trees and graphs.

The algorithm starts with a root node and first visits the node itself. Then traverse its adjacent nodes, then traverse its second-level neighbor nodes, third-level neighbor nodes, and so on.

Leetcode question

Analyzing conditions

path sum

Analyzing conditions

The maximum depth of a binary tree

Preorder traversal: root node [left subtree set] [right subtree set]

Post-order traversal: [left subtree set] [right subtree set] root node

Used to determine the root node

In-order traversal: [left subtree set] root node [right subtree set]: determine the left and right boundaries based on the root node position

This is the key to solving the problem. From these relationships, a recursive formula can be derived

key: the value of the node

value: the index of the node in the array

Pink = left subtree, red = root node, green = right subtree

Bubble Sort

Simple selection sort

The idea is still binary search, which is to find the value of val^2 closest to x by continuously compressing the sample space by binary division.

Note that what you are looking for is the mid of the square number closest to x

Use the mid of conventional binary interpolation search to split the array, determine which part of the two divided parts is ordered, and use the ordered part to determine the boundary of the binary search

Pay attention to the judgment of whether target is within the interval

Initial conditions: left = 0, right = length-1

When terminating: left > right

Find left: right = mid-1

Search to the right: left = mid 1

The search criteria can be determined without comparing to both sides of the element

No post-processing is required because at each step you are checking whether the element was found. If you reach the end, you know the element was not found.

At the end of the loop left = right 1 will return the target right neighbor index

Initial conditions: left = 0, right = length

When terminating: left == right

Find left: right = mid

Search to the right: left = mid 1

The search condition requires access to the element's immediate right neighbor. At this time right = length - 1

Post-processing is required. The loop/recursion ends when you are left with 1 element. The remaining elements need to be evaluated to see if they meet the criteria.

At the end of the loop left = right will return the coordinates of target

The idea of ​​​​solving the problem is to sort. The simplest way is to use the API as shown above. Of course, you will not be able to pass the interview when you write like this.

Using PriorityQueue limited queue

This question tests the sorting algorithm. Only handwritten sorting can meet the interviewer's test points.

Experience is sorted data. The basic idea is double pointers. The key is that the starting value is 1 and the current value is used to compare the next one -> num[i] != num[i-1]. Time O(n), space O(1)

This question is more difficult than the previous question. Two identical elements are allowed, and the experience is still that of a sorted array. What comes to mind is still double pointers, but it is not easy to implement.

A more awesome way to solve problems: compare sizes, the boss on LeetCode is awesome. Time O(n), space O(1)

Based on this, we get the goal of deleting k duplicate items in the sorted array.

If it doesn't work the right way, let's do it the other way around. Traverse from the tail. Time O(n), space O(1)