A few days ago , A round of Baidu interview questions from a former colleague , It's not too hard , And then came up with , I joked with the interviewer because the topic was simple . If you have time, you may as well have a look at it as a dessert (^o)/~

Personally, I feel that this belongs to the kind of topic that I will definitely meet when I see it , If you haven't been exposed to this kind of similar leetcode In terms of the title , Think about it is relatively simple .

But it's still out today , Share with you

The story begins →_→

1

subject

It is required to print out the tree information in the following format , Looking at the very intuitive print results

Required output format

A ->  first line B C ->  The second line D E F ->  The third line G H ->  In the fourth row 

It is to print nodes according to the given format

2

Solution

It is obvious that , While achieving this result , The general solution must be based on the way we have seen in the past

While traversing the hierarchy , Record the actions of each line feed operation

Before all this , Let's give the node information first , So that the binary tree in the figure can be operated clearly later

【 utilize Python see , Simple and intuitive 】

class TreeNode:    
def __init__(self, value):        
self.val = value  
#  Node values  
self.left = None  
#  To be a child  
self.right = None  
#  Point to the right child 

Need to review the level of traversal code can turn to the end of the article , The display of hierarchical traversal is carried out , Here's the past C Language implementation code

Because the topic requires printing node information at the same time , Information about the row and column of the node is required

Using the characteristics of hierarchical traversal （ a key ！ a key ！ a key ！ After all node elements of the current layer are queued , The last node element of the upper layer will pop up ）, Initialize two pointers last and cur

• last Point to the rightmost node of the upper layer
• cur Is the current node location 【 The node entered into the queue 】

Only when the element pops up And last Points to the same node , explain cur Also traversed to the right side of the current layer . here , Can make last = cur

The detailed process , Look below [ Long, long, long …] chart 【 Click to enlarge 】

above , Based on the given tree structure, detailed description is given , For your reference . Another person doesn't like moving pictures very much , The reason is that when you want to see every step clearly , It's not easy to control

For queue operations , utilize Python Of list The data structure is implemented in the following way

#  The team list.append('A')
#  Out of the team list.append(0)

Here's the full code , And give the code of the construction tree that has been traversed hierarchically

3

Complete code

It can be directly posted to your own environment for implementation ~

# -*- coding:utf-8 -*-
# !/usr/bin/env python
#  Tree node class class TreeNode:    
def __init__(self, value):        
self.val = value        
self.left = None        
self.right = Nonedef level_order_traverse(root):    
if not root:        
return        
#  queue queue    
queue = [root]    
while len(queue) > 0:        
node = queue.pop(0)        
print(node.val, end=" ")        
if node.left:            
queue.append(node.left)        
if node.right:            
queue.append(node.right)def level_order_traverse_datail(root):    
last, n_last = root, root    
i = 1    
if not root:        
return    
#  queue queue    
queue = [root]    
while len(queue) > 0:        
node = queue.pop(0)        
print(node.val, end=" ")        
if node.left:            
n_last = node.left            
queue.append(node.left)        
if node.right:            
n_last = node.right            
queue.append(node.right)        
#  When the pop-up node is last Point to the node of , Make  last = n_last        
if last is node:            
last = n_last            
print(" ->  The first  %d  That's ok " % i)            
i = i + 1if __name__ == "__main__":    
#  The new node     
node_A = TreeNode("A")    
node_B = TreeNode("B")    
node_C = TreeNode("C")    
node_D = TreeNode("D")    
node_E = TreeNode("E")    
node_F = TreeNode("F")    
node_G = TreeNode("G")    
node_H = TreeNode("H")    
#  Building a binary tree     
#      A    
#    /   \    
#   B     C    
#  /     / \    
# D     E   F    
#      / \    
#     G   H    
node_A.left, node_A.right = node_B, node_C    
node_B.left = node_D    
node_C.left, node_C.right = node_E, node_F    
node_E.left, node_E.right = node_G, node_H    
#  Print node elements     
print(" Hierarchy traversal results ：")    
level_order_traverse(node_A)    
print("\n Hierarchy traversal results ( Print line number )：")    
level_order_traverse_datail(node_A)

Due to the length limitation of the article , Please click the business card below to receive the interview information displayed above

↓↓↓