One, foreword

Medium difficulty mainly examines CRUD operations combining the properties of binary trees, which are based on traversal of binary trees.

Binary trees are subsets of graphs, so the following two search ideas are also applicable:

  • DFS (depth-first search) : recurse down the root node and back up the leaf node;

  • BFS (breadth-first search) : Access at the level of the binary tree, usually using queues to hold nodes at each level.

Since the binary tree itself is defined recursively, the code is easier to understand when handled recursively. However, the efficiency of recursion is relatively slow, mainly because: the time and space cost of a function to be called is very high, and too many recursions may lead to the problem of call stack overflow. The last article also mentioned that tail-recursion could be written to allow the JavaScript engine to optimize the recursion into iteration to solve performance problems.

But in some cases, tail recursion is not that easy to write, so this article will present both recursive and iterative solutions.

Next, through specific topic analysis, we will understand the application of DFS and BFS search ideas in binary trees.

102. Hierarchical traversal of binary trees

Given a binary tree, return the value of the nodes traversed hierarchically. (That is, layer by layer, all nodes are accessed from left to right).

1, the BFS

The problem requires hierarchical traversal of nodes, which is well defined by the IDEA of BFS search, so the code is easy to understand.

In this case, we need to use queues to store nodes that need to be accessed at each layer. We need to pay special attention to the first-in-first-out nature of queues. In this case, each layer needs to traverse from left to right, so we need to queue the left subtree first.

2, DFS

Using the DFS search idea, it is necessary to record the hierarchical information of the current node in the recursive process:

Backward traversal of binary trees

Given a binary tree, return its backward traversal.

The most common types of traversal in binary trees are defined by the order in which the root nodes are accessed:

  • Sequential traversal: first visits the root, then traverses the left subtree, and finally traverses the right subtree;

  • Middle order traversal: first middle order traverses the left subtree, then visits the root, and finally middle order traverses the right subtree.

  • Back-order traversal: first back-order traversal of the left subtree, then back-order traversal of the right subtree, and finally access the root;

Take the post-order traversal of this problem as an example, try two different methods of recursion and iteration:

1, recursive implementation of DFS

From the definition, you should be able to imagine how the recursive code would be written:

2. Implement DFS iteratively

It is not easy to understand why DFS is implemented by iteration, mainly because iteration cannot backtrack up like recursion, so the root node cannot be guaranteed to be accessed last in the process of iterating down.

Let’s review the final sequence of the post-order traversal:


     
    
      
    Left subtree --> Right subtree --> root
    
     
Copy the code

If you had to access the root node first, would you get a sequence like this:


     
    
      
    Root --> right subtree --> left subtree
    
     
Copy the code

Finally, the sequence is reversed, is not the solution required in this case after the order traversal!

Here, we make use of the last-in, first-out feature of the stack to push the right subtree to the stack last, so that the right subtree conducts in-depth search first:

Iv. 987. Vertical order traversal of binary trees

Given a binary tree, a vertical traversal returns the value of its nodes. For each node located at (X, Y), the left and right children are located at (x-1, y-1) and (X+1, y-1) respectively. We move a vertical line from X = -infinity to X = +infinity, and every time the vertical makes contact with a node, we report the node’s value from top to bottom (the y-coordinate is decreasing). If two nodes are in the same position, the node value reported first is smaller. Returns a list of non-empty reports in x-coordinate order. Each report has a list of node values.

Finally, we will start the explanation of Medium difficulty with this question.

This problem requires us to find the vertical order traversal sequence, so first or first traversal binary tree, here the recursive implementation of DFS to traversal binary tree.

In the process of recursion, coordinate information needs to be transferred downward, and triplet information (X coordinate, Y coordinate, node value) of each node is recorded through HashTable, so as to construct vertical sequence subsequently:

After the coordinate is obtained, the triplet needs to be sorted comprehensively, and finally the vertical order traversal sequence is constructed according to the X coordinate, with time complexity O(nlogn).

Write in the last

Algorithms as basic computer disciplines, using JavaScript brush, there is no loss of ε=ε=ε= old (゜ _ ゜ロ゜;) ┛.

This series of articles will provide summaries of each algorithm on three levels of difficulty (easy, medium, and hard). In the simple difficulty, we will introduce the basic knowledge and implementation of the algorithm, and in the other two difficulties, we will focus on the idea of solving the problem.

In each summary, some key topics will be selected and explained. For a complete list of problems, please refer to “LeetCode Journey of Front End Engineers”.

If this article has helped you, feel free to like it or follow it to encourage bloggers.

  • The front End Engineer’s LeetCode Journey — Binary Tree Easy

  • https://github.com/15751165579/LeetCode

Focus on not getting lost.

Quality content we all “watch”