Shulou(Shulou.com)05/31 Report--

In order to solve the problem of hierarchical traversing binary tree, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

Primary level: give a binary tree, output according to the hierarchy, the first line outputs the nodes of the first layer, the second line outputs the second layer, and so on.

Advanced: what if I only give you extra space for O (h)? (h is the height of the tree)

A:

Initial stage: the width (breadth) first search algorithm BFS is adopted. The nodes of one layer are stored in a queue, and the nodes of the next layer are extended through one layer of nodes. There are two ways to achieve this: one way is to store the number of layers in the queue at the same time, and if you find that the number of layers is different, you will break the output line; the other way is to record the head and tail of each layer, and loop out each layer with more than one layer. Time complexity O (n), space complexity O (n)

Advanced: iterative search is used. Iterative search means that a layer limit x is set, and the depth-first search is used to search down, and every time x is found, there is no further recursion. The search for each layer is achieved by gradually relaxing x, that is, x enumerates from 1 to h (h is the height of the tree). Time complexity O (nh), space complexity O (h). Iterative search is a common method to replace width-first search in the case of insufficient space. It's a way of exchanging time for space.

This is the answer to the question about how to traverse the binary tree in layers. I hope the above content can be of some help to you. If you still have a lot of doubts to be solved, you can follow the industry information channel to learn more about it.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.